지민 개발 블로그

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이과정 ①문제 바라보기 이 문제는 타일링문제로 dp문제 중 하나이다. 저번에 타일링 문제를 풀었었는데 그때 점화식으로 푼 기억이 난다. 사실 dp문제가 점화식으로 많이 풀리긴 하더라.. 고통을 받으며 점화식을 찾게 되었다. dp[i] = dp[i-1] + dp[i-2] 였던 것임! ②아이디어 열기 신나는 마음으로 코드를 짰는데.. 나름 짧아서 예뻤다. 근데 메모리초과가 떴다!! 오마이갓.. 사실 저 ..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 풀이과정 ①문제 바라보기 굉장히 와닿지 않았다. 굉장히 굉장히.. 그래서 recursive로 먼저 코드를 작성해보았다. 그런데 문제의 설명대로 역시 15 15 15를 넣을 경우 굉장히 연산 속도가 느렸다. 조금 생각을 해보니 위의 코드는 탑다운 방식처럼 재귀를 사용해서 느린 것 같다. 그래서 반복문을 활용하는 보텀업 방식을 사용하면 해결 될 수 있을거라는 생각을 하게 되었다. 그런데 문제는, 값이 a..

문제 풀이: 이 문항은 dp문항이다. 처음에 input을 arr list를 만들어 따로 받았는데, 그럴 필요가 없었다. arr로 따로 만들게 된 이유는, 이때까지 풀었던 몇 가지 dp 문항들이 min(dp[i-1] + arr[i],dp[i]) 이런식으로 자꾸 비교하면서 들어오길래 이상하게 생각없이 arr를 무작정 만들었었다. 그런데 해결이 안되니, 근본적인 이유는, 그냥 R일 때 G일 때 B일 때를 모두.. dp로 해보면 된다는 점이었음. '모두'라 함은 작을 수 있는 가능성이 있는 경우를 뜻함. 그래서, 시작이 무엇이니에 따라서 case가 3가지가 나오고 그때마다 그냥 가장 적게 드는 값을 탐색하다보면 답이 나온다. 코드: N = int(input()) dp = [] for _ in range(N): ..