Algorithms63 백준 1149. RGB 거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 색이 연속되지 않게 합을 앞에서부터 쌓아서 정리할 생각을 해봤다. n = int(input()) arr = [] for _ in range(n): arr.append(list(map(int, input().split()))) for i in range(1, n): arr[i][0] = min(arr[i-1][1], arr[i-1][2]) + arr[i][0] arr[i][1].. 2022. 6. 27. 백준 1912. 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 이중 반복문을 쓰자니 시간 초과가, 그렇다고 2000개 크기의 배열을 생성하자니 메모리 초과가 떠서 고민했던 문제. 문제를 풀다보니 DP는 약간 수열틱(?) 하구나 라는 감을 잡게 되었다. 예제 기준으로 최대 부분합 후보를 나열해보면 다음과 같다. 최대 부분합 후보를 계속 구하다가, 후보가 특정 한 값보다 작아지면 최대 부분합 후보 탈락이므로 업데이트를 해주면 된다. 위 경우에는 -14 +12 = -2 < .. 2022. 6. 26. 백준 1904. 01타일 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 우선 패턴을 파악해보면 된다. 피보나치 수열과 같은 패턴이 된다. 이를 dp를 이용하여 구현하면 된다. 단, 값이 갈수록 기하급수적으로 커지기 때문에 정수 값을 금방 넘어가버리므로 값을 넣을 때부터 15746으로 나눈 나머지를 넣어줘야 메모리 초과가 일어나지 않는다. n = int(input()) lst = [0] * 1000001 lst[1] = 1 lst[2] = 2 for i in range(3,.. 2022. 6. 24. 백준 9184. 신나는 함수 실행 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net Dynamic Programming에서는 재귀를 전혀 사용하지 않는 줄 알아서 헤매었으나 동적 프로그래밍의 정의를 검색해본 후로 이해가 갔다 ㅋㅋㅋㅋ 단순히 말하면 이전에 구한 답을 재활용하면 된다. def w(a, b, c): if a 20: return w(20, 20, 20) if dp[a][b][c]: return dp[a][b][c] if a < b < c: dp[a][b][c] = w(a,.. 2022. 6. 23. 이전 1 2 3 4 5 6 7 ··· 16 다음
