728x90 DP16 [python] 백준 2631 줄세우기 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제 해결 LIS (Long Increase sequence) 구하는 문제 가장 긴 증가하는 수열이 만들어 진 부분 수열을 구한다음 그 원소들을 빼고 나머지를 필요한 곳으로 옮기면 되는 것이다. CODE import sys input = sys.stdin.readline n = int(input()) A = [0]+[int(input()) for _ in range(n)] dp = [0 for _ in .. 2023. 3. 20. [python] 백준 16194 카드 구매하기 2 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 해결 i개를 사는 방법의 수는 매우 많다. 하지만 i개를 사는 방법의 가지수는 (1개 사는 방법+i-1개 사는방법) + (2개 사는 방법 + i-2개 사는 방법).... + i개 통째로 사는 방법으로 나타낼 수 있다. dp[i]를 i개 사는 최소 비용이라 하자. dp[i] = dp[i-j] + P[j]로 나타낼 수 있다. (j=1,2,3,4,...i) P[j]는 j개를 묶음으로 살 때 비용 CO.. 2023. 3. 18. [python] 백준 9625 BABBA https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 문제 해결 A→B, B→BA로 바뀌고 k번째 바뀌었을 때 A, B의 개수를 구하는 것이므로 DP를 이용하는 것이 편할 것이란 생각이 든다. dp[i][0]는 i번 눌렀을 때 A의 개수, dp[i][1]은 i번 눌렀을 때 B의 개수로 정의한다. dp[0][0] = 1, dp[0][1] =0 에서 시작 dp[i][0] = dp[i-1][1] 이고 dp[i][1] = dp[i-1][0] + dp[i-1][.. 2023. 3. 17. [python] 백준 5557 1학년 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 해결 이전 항들의 영향을 받는다. 이전 항들까지 더하기, 빼기를 이용해서 만들 수 있는 것은 0이상 20 이하여야 한다. dp로 가지수를 만들수 있다. dp[i][j]를 j-1번째 항까지 더하기 빼기를 이용해서 i를 만들 수 있는 가지수를 나타낸다. dp[A[n-1]][n-2] 의 값을 구하면 된다. CODE import sys input = sys.stdin.readline n = .. 2023. 3. 15. 이전 1 2 3 4 다음 728x90
