본문 바로가기
728x90

DP16

[python] 백준 17070 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 해결 파이프는 그래프에서 0좌표에만 놓을 수 있다. (1은 벽이므로) 파이프를 놓는 방법의 수는 이전 장소 (r,c) 좌표면 (r-1,c), (r,c-1), (r-1,c-1) 좌표의 영향을 받는다. 각 좌표에 어떻게 놓느냐에 따라 경우의 수가 달라진다. 문제의 그림을 참고하는 것이 좋다. DP를 3차원을 이용해서 풀면 충분히 쉽게 풀 수 있다. CODE n = int.. 2023. 3. 9.
[python] 백준 2096 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 해결 사실 문제 자체는 매우 쉽다. (dp를 이용해서 0열, 1열, 2열에 각각 올 수 있는 이전 행 최고 누적합을 가져오서 더하면 되므로) 하지만 메모리가 4MB 밖에 안주어진다. 정확한 양은 체감을 못해도 평소 250~500MB 되는 문제도 많은 것을 보면 엄청 적다는 것을 알 수 있다. 따라서 리스트를 n행 모두 사용하는 것이 아니라(dp[0], dp[1], .... 사용하면 메모리가 커진다..) 한.. 2023. 3. 7.
[Python] 백준 2193 이친수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 해결 - 다이나믹 프로그래밍(dp)인 것은 쉽게 눈치 챌 수 있다. - n자리 이친수 개수를 dp[n]으로 놓을 때 dp[n] = dp[n-1] + dp[n-2]임을 알아야 한다. 그림판으로 그리면 dp[n]=dp[n-1] + dp[n-2]임을 알 수 있다. CODE import sys input= sys.stdin.readline n = int(input()) dp = [0 fo.. 2022. 12. 22.
[Python] 백준 25682 체스판 다시 칠하기 2 https://www.acmicpc.net/problem/25682 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 해결 1018번과 같은 유형이지만 시간초과 압박이 있다. https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 하지만 별 생각이 안나서 비슷하게 풀어 봤다. CODE i.. 2022. 12. 22.
728x90