문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 설명 이 문제는 DP로 풀 수 있다. 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정의하기 이 세가지 과정을 거쳐 문제를 풀 수 있다. 1. 테이블 정의하기 D[i]= i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 2. 점화식 찾기 D[12] =? D[1]부터 D[11]까지의 값을 다 알고 있다고 가정하면 1, 2, 3, ..., 11을 1로 만들기 위한 최소 횟수를 다 알고 있다고 하면 이런 상황에서 D[12]를 구하는 방법은 12에서 할 수 있는 연산을 생각하면 된다. D[4], D[6..

문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 설명 처음엔 이 문제가 이해가 잘 안갔다. 설명해보자면 만약에 18짜리 중량인 물체가 있다면 버틸수 있는 최대 중량이 6인 로프 3개로 물체를 들 수 있다. 반대로 위에서 말한 6짜리 로프 3개로는 로프 1~3개를 이용하여 6, 12, 18 짜리 중량인 물체를 들수 있는데 그 중에 최대 중량은 18이기 떄문에 답은 18이 된다. 로직을 생각해보면 만약에 버틸 수 있는 최대중량이 1,..

문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 설명 회의시간들을 끝나는시간이 빠른순으로 정렬하고 끝나는시간이 동일하다면 시작하는 시간이 빠른순으로 정렬한다. (회의시작과 끝나는시간이 같을수도 있기 떄문에!!) 따라서 시작하는 시간, 끝나는 시간을 pair 에 반대로 저장해주었다. t는 현재 시간이며, 0으로 초기화 해두고 제일 먼저 끝나는 회의시간을 t로 초기화 해두고 cnt값도 증가시킨다. for문을 돌리며 다음 회의 시작시간 > n; for (int i = 0; i > s[i].second >> s[i].first; }..

문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 설명 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식이다. 그리디 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 왜 그리디 알고리즘 인가?? 이렇게 단순하게 거스름돈을 지불해야 하는 상황에서 큰 동전만을 생각하고 다른 동전은 생각하지 않기 때문에 매순간 최적이라고 생각되는 경우를 선택하는 그리디 알고리즘이라..

문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i > n; for (int i = 0; i > arr[i]; } int x; cin >> x; int ..