728x90 반응형 DP18 [백준] 11727번: 2×n 타일링 2 - python https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 타일링 버전 2가 있길래 기대하며 바로 풀었다. 비슷하네 라고 생각햇는데 비슷했다. 이것도 처음부터 생각해가면서 얼마씩 증가할려나 라는 감으로 때려 맞춰서 풀었다. 그리면서 하면 패턴을 쉽게 찾을 수 있는 문제인 것 같다. i-2 와 연관관계과 있을 것 같아서 바로 때려맞춘 코드 바로 틀렷다고 해서 생각해보니 홀수 짝수 증감을 나눠서 생각해야되는 것 같았다. n = int(input()) dp = [0] * 1001 dp[1].. 2024. 3. 28. [백준] 11726번: 2×n 타일링 - python ×https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 기본 DP문제. 항상 DP를 풀면서 생각한건 고등학교때 수2?에 나오는 점화식 문제를 생각이 난다. 저장소 만든 다음에 설마 이건가 하고 점화식을 만들어서 대입하면 풀린다. 고딩때도 비슷햇다 n = int(input()) dp = [0] * 1001 dp[1] = 1 dp[2] = 2 dp[3] = 3 for i in range(4, 1001): dp[i] = dp[i-1] + dp[i-2] print(dp[n] %.. 2024. 3. 28. [백준] 1149번: RGB거리 - python https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 쉽지 않았던 dp문제. 값을 업데이트 해나가는 방식이 접근하기 어려웠다. 최소값은 전에 있는 것만 비교하면 되기 때문에 i-1과 비교하여 그 자리를 업데이트한다. 그러면 각 R G B에 대한 최소값이 업데이트 되는데 마지막에 그 3가지 중 최소값을 찾으면 되는 문제이다. n = int(input()) arr = [] for i in range(n): R, G, B = map(.. 2024. 3. 28. [백준] 9657번: 돌 게임 3 - python https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 저번에 처음 돌 게임 1을 푼 기억이 생각났다. 확실히 업그레이드가 되었다. 가지치기를 하면 훨씬 빠르지만 게을러서 그냥 제출헀다. n = int(input()) dp = [0] * 1001 #0은 상근 1은 창영으로 설정 dp[1] = 0 dp[2] = 1 dp[3] = 0 dp[4] = 0 dp[5] = 0 dp[6] = 0 # 4 1 1 dp[7] = 1 # 1 4 1 1 for i in range(8, 1001): if dp[i-1] == 1 or dp[i-3] == 1 or dp[i-4] == 1: dp[.. 2024. 3. 27. 이전 1 2 3 4 5 다음 728x90 반응형
