코딩89 [백준] 11052 - 카드 구매하기 (Python) 문제 출처: www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 풀이 : 점화식을 DP[i] = i개를 샀을때 최대비용 으로 잡고 풀었다. 점화식을 이용하면 DP[i] = max(DP[i-1] +P[1] , DP[i-2]+P[2] , .... , DP[i-i] + P[i]) 까지를 고르면 된다. (필자는 다이나믹 프로그래밍을 풀 때 최대한 다른사람에게 미루기 전법을 쓰는데 이게 그 전법이다. DP[i] 이전의 것들이 다 구해졋다고 생각했을때 DP[i]만 생각하는 .. 2021. 3. 25. [백준] - 2156 포도주시식 (Python) 문제 출처: www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 풀이: 문제의 조건이 연속하는 3잔을 마실 수 없다는 것이다. 이에 대해서 i번째 포도주에 대한 포지션을 다음과 같이 생각할 수 있다. i 번째 포도주 앞에 1잔 먹고 i번째 포도주 먹는 경우 : A (n-2번째 잔은 마실 수 없다) i번째 포도주 바로 앞에는 안먹고 그전꺼 1잔 먹고 i번째 먹는경우 : B (n-1번째 잔은 마실 수 없다) i번째 포도주 안먹고 앞에서 연속 2잔 먹는경우 : C.. 2021. 3. 25. [백준] 2293 - 동전1 (Python) 문제 출처: www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이: DP 문제는 보통 점화식을 찾으면 끝나기 때문에 점화식을 찾으려 했는데 아무리 봐도 점화식이 안 보여서 애먹은 문제이다. 이 문제는 코인별로 점화식을 따로 봤어야 하는 문제인데 난 한 번에 같이 보려다 보니 어려웠다. 직접 예제를 적어가면서 보면 더 쉽게 보인다. k=10이고 동전은 1,2,5인 경우를 보자 k 1 2 3 4 5 6 7 8 ... 1원 1 1 1 1 1 1 1 1 ... .. 2021. 3. 20. [백준] 11727 - 2xn 타일링2 (Python) 문제 출처: www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 풀이: 앞서 본 2xn 타일링 과 매우 흡사한 문제이다. 이문제의 경우 기존에 문제에 2x2타일이 생긴 경우이다. 정답을 듣기전에는 사고하기가 어려울 수 있는데 간단하게 생각하면 기존 2xn 타일링 문제의 점화식을 그대로 가져오되, 2x2 짜리 타일은 1x2짜리 타일 2개를 이은거와 같은 형태이므로 2x2 타일을 쓸 경우와, 1x2짜리 타일을 쓸 경우를 따로 샌다고 생각해보면 두가지다 결국 dp[n-2] 가 된다. 따라서 .. 2021. 3. 17. 이전 1 2 3 4 5 6 7 ··· 23 다음 반응형
