아이테킨의 끄적끄적

역시나 DP문제이므로 처음엔 점화식을 구해보려고 생각해보았다. 그러나 이전처럼 뭔가 깔끔하고 정리가 딱 되는 점화식이 생각나지 않아서 각 층마다의 최대값을 모두 구하는 방식으로 문제를 풀었다. 각 층의 첫번째 값과 마지막 값은 바로 직전 층의 값을 그대로 더해주면 되었고 그 이외의 값들은 위에 층의 더해질 수 있는 두가지 값 중 큰 값을 더해주는 방식으로 풀었다. 코드 # 1932 - 정수삼각형 # 아이디어는 각 층마다 최대값을 다 구한뒤 최대값을 찾아서 출력한다 import sys input = sys.stdin.readline n = int(input()) triangle = [] for _ in range(n): triangle.append(list(map(int,input().split()))) ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP문제를 계속해서 풀면서 느끼는점은 결국 점화식을 생각해내는 것이 핵심 포인트인것 같다. 문제를 어떻게 쪼개고 반복해서 연산한다음 합칠것인지 충분히 고민하고 문제를 푸는게 오히려 더 빠르고 정확하다는 생각이 든다. 점화식 i번째에 빨강을 칠할 때 최소값 = i번째 빨강의 비용 + min(i-1번째 파랑의 최소값, i-1번째 초록의 최소값) 코드 # 1149 - RGB거리 #..

이 문제도 점화식을 구하면 쉽게 풀 수 있는 문제다 그림을 유심히 살펴보거나 혹은 결과들을 유심히 살펴보면 숫자들간에 규칙이 있는것을 발견할 수 있다. (사실 다른 더 논리적이고 멋있는 해설이 있기야 하겠지만 나는 이렇게 풀었다...;;) 점화식 $$ a_n = a_{n-5} + a_{n-1} $$ 코드 # 9461번 - 파도반 수열 import sys input = sys.stdin.readline t = int(input()) for _ in range(t): dp = [0] * 101 dp[1] = 1 dp[2] = 1 dp[3] = 1 dp[4] = 2 dp[5] = 2 n = int(input()) for i in range(6,n+1): dp[i] = dp[i-5] + dp[i-1] print..

일단 이 문제는 점화식으로 표현할 수 있다면 쉽게 풀 수 있는 문제다. $$A_n = A_{n-1} + A_{n-2}$$ 처음 1,2 까지의 값만 다른 피보나치 수열이다. 점화식을 알았으니 반복문 또는 재귀함수를 이용해서 풇어주면 된다. 반복문을 이용해서 풀어보았다. # 1904번 - 01타일 # 반복문을 이용해서 - 바텀업 import sys input = sys.stdin.readline n = int(input()) tile_list = [0]*(n+1) tile_list[1] = 1 tile_list[2] = 2 for i in range(3,n+1): tile_list[i] = (tile_list[i-1] + tile_list[i-2])%15746 print(tile_list[n]) 이때 주의해..

∴다이나믹 프로그래밍에 대한 개념정리 및 예제풀이 마지막으로 DP 정복하는것을 향해서!!! 다이나믹 프로그래밍(Dynamic programming, DP)란? 다이나믹 프로그래밍이란 복잡한 하나의 문제를 간단한 여러개의 중복되는 문제로 나누어 같은 방식으로 풀어 답을 구하는 방법을 말한다. 나는 보통 동적(Dynamic)이라는 용어를 보면 '계속해서 움직이는' 이라는 뜻으로 이해했다. 그러나 여기서의 동적(dynamics)이라는 단어는 DP를 이해하는데 직관적으로 도움을 주지 못하는듯 하다. 뒤에서 언급하겠지만 그보다는 '작은 중복문제들을 기억하며 푼다'라는 의미로 받아들이는 것이 좋을 것 같다. 그래서 앞으론 dyanmic programming보다는 DP라고 부르려고 한다. (사실 이렇게 해야 나도 헷..