목록C++ (66)
블로그 언저리인 무언가
문제 : 1138 한 줄로 서기 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 사람의 수와 그 사람의 왼쪽에 있는 키가 큰사람의 수가 주어졌을 때 줄을 어떻게 세워야 하는지 출력하는 문제이다. 자신보다 키가 큰 사람이 왼쪽에 그 숫자만큼 위치하기 위해서는 최소한 그만큼의 빈 공간이 있어야 하는 것을 전제로 그리디 하게 접근하면 쉽게 풀 수 있다. Code #include #define ll long long using namespace std; ll N, arr[10]; int main(){ ios:..
문제 : 18115 카드 놓기 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net 카드를 내려놓은 순서가 주어질 때, 원래의 카드 순서를 복구하는 문제이다. deque 자료형을 이용해 앞뒤로 집어넣은 후 출력하면 된다. Code #include #define ll long long using namespace std; ll N; vector arr; deque dq; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i=0;i> a; arr.p..
문제 : 2529 부등호 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 부등호 기호가 나열되어있는 배열이 주어질 때, 서로 다른 한 자릿수 숫자를 넣어 만족하는 가장 큰 수와 가장 작은 수를 찾아 출력하는 문제이다. 백트래킹 기법을 활용해서 모든 경우의 수를 확인해서 비교하면 된다. Code #include #define ll long long #define INF 1e15+7 using namespace std; ll N, visited[10], mn=INF, mx=-1; vector arr; void ..
문제 : 2758 로또 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net M이하의 수중에서 N개의 수를 뽑을 때, 앞의 수보다 2배가 되는 규칙을 따를 때 경우의 수를 세는 문제이다. 앞의 수 중에서 현재수/2보다 작은 수들의 경우의 수를 모두 더하는 DP테이블을 만들어 채운 후 모두 더해 출력하면 된다. Code #include #define ll long long using namespace std; ll T, N, M, arr[15][2005]; int main(){ ios::sync_with_stdio(0); c..
문제 : 5972 택배 배송 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 헛간의 개수와 그를 잇는 길에 있는 소의 수가 주어질 때, 최소한의 여물을 지불하는 방법을 찾는 문제이다. 양수 간선만 존재하므로 다익스트라 알고리즘을 활용하여 풀면 된다. 지금까지 변수명을 visit으로 많이 사용했는데 변수명이 모호하다고 컴파일 에러가 나서 앞으로는 visited라는 변수명을 사용해야겠다. Code #include #define ll long long #define INF 1e9+7 using namespace std; s..
문제 : 20114 미아 노트 20114번: 미아 노트 첫째 줄에 원래 문자열의 길이 N, 세로로 번진 글자의 개수 H, 가로로 번진 글자의 개수 W가 주어진다. (1 ≤ N ≤ 100, 1 ≤ H ≤ 10, 1 ≤ W ≤ 10) 둘째 줄부터 H개의 줄에 걸쳐 N × W 길이의 문자열이 www.acmicpc.net N길이의 문자열이 H*W크기만 큼 번지고 지워졌을 때, 원래 문자열을 복구해서 출력하는 문제이다. 현재의 문자가 원래 문자열의 어느 위치인지 찾아서 갱신해주고 찾지 못한 위치의 문자는 '?'을 출력해주면 된다 Code #include #define ll long long using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0);..
문제 : 4781 사탕 가게 4781번: 사탕 가게 각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개 www.acmicpc.net 사탕가게에 있는 모든 사탕의 가격과 칼로리가 주어질 때, 보유한 금액 내에서 칼로리합이 가장 크도록 사탕을 사는 문제이다. 같은 사탕을 여러 개 살 수 있기 때문에 DP 알고리즘을 사용해서 배열을 채우면 된다. 입력으로 주어지는 실수를 정수로 바꿀 때 오차가 날 수 있으므로 반올림을 위해서 0.5를 더한 후 바꾼다. Code #include #define ll long long using namespa..