https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 필요한 배경지식 다이나믹 프로그래밍 문제 해결 방법 동전의 순서는 중요하지 않으므로 동전별로 차례대로 K원을 몇개나 만들 수 있는지 다이나믹 프로그래밍 하면 된다. 문제에서 주어진 입력으로 예를 들어보겠다. dp[K]를 'K원으로 만들 수 있는 동전조합의 수' 라고 할때 먼저 base case로 dp[0] = 1 을 정의할 수 있다. ('0원을 만들 수 있는 경우는 한가지'라고 인..
https://www.acmicpc.net/problem/10564 10564번: 팔굽혀펴기 각각의 테스트 케이스에 대해서, 동혁이가 응원하는 팀이 득점한 점수의 최댓값을 출력한다. 만약, 불가능한 경우에는 -1을 출력한다. www.acmicpc.net 1년전쯤 한창 DP문제를 풀며 자신감에 차 있을때 풀다가 벽을 느끼며 포기했던 문제였다. 이제는 풀 수 있을것 같아서 도전해 봤는데, 쉽진 않지만 생각하는 대로 문제가 풀리니 뿌듯했다. 필요한 배경지식 다이나믹 프로그래밍 BFS 문제 해결 방법 배낭문제(Knapsack Problem) 풀듯이 문제를 해결했다. 득점의 종류를 이용하여 나올 수 있는 총 팔굽혀펴기의 수를 탐색하는 방법이다. bool dp[i][j] : 총 i점일때 j번 팔굽혀펴기가 가능한가 ..
https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 필요한 배경지식 다이나믹 프로그래밍 조합론 - 파스칼 항등식 문제 해결 방법 N=2, M=2 일때 나올 수 있는 문자열을 사전순으로 나열하면 다음과 같습니다. 1번째 문자열 : aazz 2번째 문자열 : azaz 3번째 문자열 : azza 4번째 문자열 : zaaz 5번째 문자열 : zaza 6번째 문자열 : zzaa 문제에서 K=2로 주어진다면 2번째 문자열인 azaz를 출력해야 합니다. 어떻게 출력해야 ..
www.acmicpc.net/problem/2031 2031번: 이 쿠키 달지 않아! 첫 번째 줄에 4개의 자연수 T, N, D, K가 주어집니다. (1 ≤ T ≤ 109, 1 ≤ N ≤ 106, 1 ≤ D ≤ 109, 1 ≤ K ≤ 10) 두 번째 줄에 N 종류의 음식 각각을 먹을 시각을 나타내는 N 개의 자연수 a1, ..., aN이 주어집 www.acmicpc.net 재미있는 DP문제였습니다. 다이어트 효과가 최대가 되려면 다이어트가 효과가 유지되는 시간안에 음식이 가장 많이 포함되어 있어야 합니다. 우선 단순하게 K=1일때의 문제를 생각해 봅시다. 위에서 정의한 문제를 'D만큼의 범위안에 포함할 수 있는 원소의 최대 개수'로 치환할 수 있습니다. 그렇다면 이 문제는 정렬과 이분탐색을 이용하면 O(..