728x90 다이나믹 프로그래밍18 [python] 백준 9456 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 해결 dp로 문제를 해결 해야할 것 같음 dp[0][n]을 n번째 열에는 스티커를 떼지 않고 얻을수 있는 점수 최대 값을 표현하고 dp[1][n]을 n번째 열에 1행 스티커를 땔 때 얻을 수 있는 점수 최댓값을 표현 dp[2][n]을 n번째 열에 2행 스티커를 땔 때 얻을 수 있는 점수 최댓값을 표현한다고 하고 코드를 짜면 쉽게 짤 수 있다. code import sys input.. 2022. 12. 27. [python] 백준 17404 RGB거리2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 해결 R, G, B 3 가지 선택지가 있으므로 dp를 사용할 때 dp[n][0], dp[n][1], dp[n][2] 를 사용해야 할 것 같다. 비욜 cost 리스트를 만들면 dp[n][0] = cost[n][0] + min(dp[n][1], dp[n][2]) 를 사용하면 바로 전에 같은 색을 칠하지 않고 최솟값을 구할 수 있다. 그런데 문제점! 1번 집의 색과 N.. 2022. 12. 26. [Python] 백준 11057 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 해결 n자리 수일 때 앞에서부터 n-1번째 수에 무슨 수가 오느냐에 따라 n자리에 올 수 있는 숫자의 개수가 달라짐 따라서 n번째 숫자에 i가 올 경우의 수를 dp[n][i]라 하면 $$dp[n][i] = \sum_{k=0}^i dp[n-1][k]$$ 1자리 수일 때 i가 어느 수던간에 dp[n][i] = 1이므로 dp를 이용해서 쉽게 풀 수 있다. COD.. 2022. 12. 26. [Python] 백준 1309 동물원 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제 해결 뭔가 점화식 같은 느낌이 드므로 dp를 이용해야할 것 같다. dp[1] = 3 dp[2] = 7 dp[3] = 17 dp[4] = 41 (예제 입출력에 존재) 뭔가 dp[n] = 2*dp[n-1] + dp[n-2] 처럼 보이는데... 논리적으로 설명을 못하겠다... 한번 시험해 봤는데 n = int(input()) if n == 1: print(3) elif n ==2: print(7) else: dp = [0 for _ in range(n+1)] dp[1] = 3 dp[2] = 7 for i in range(3,n+1.. 2022. 12. 25. 이전 1 2 3 4 5 다음 728x90
