전체 글92 백준 1932. 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 합이 최대가 되도록 삼각형의 구성요소를 한 행당 하나씩 뽑아 구성하면 된다. 다만 이 때, 아래층에 있는 수는 왼쪽 혹은 오른쪽 위 대각선에 있는 요소만 선택할 수 있다. 단순히 위에서부터 내려오면서 합을 누적시켜 구할 수 있는데, 이 때 양쪽 끝 요소의 경우 오른쪽 대각선 혹은 왼쪽 대각선 요소가 당연히 선택되므로 이에 따른 처리를 해주고, 중간에 낀 요소들은 좌우 대각선 요소를 비교해서 더 큰 값을 넣어주면 된다. 그 후 마지막 행에서 가장 큰 요소를 찾아주면 된다.. 2022. 6. 28. 백준 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. 이전 1 2 3 4 5 6 7 8 ··· 23 다음
