알고리즘60 [Python] 백준 1958번: LCS 3 https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 1. 그렇다 3차원배열을 쓰면 쉽게 해결가능한 문제이지만 2차원배열로 풀어보았다. 2. 밑에가 3차원이고 위에가 2차원으로 풀었다. 3. 위의 방법은 권장하지않는다.. s = [] for _ in range(3): s.append(input()) dp = [[0 for _ in range(101)] for _ in range(101)] ans = 0 def maxLCS(x, y): tmp = 0 for i in.. 2021. 10. 7. [Python] 백준 17404번: RGB거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1. 각 집의 색깔마다 더할 수 있는 최솟값을 더해나간다.(이전 집과 같은 색은 안됨) 2. 마지막 집과 첫번째 집의 색깔은 달라야 한다. 3. 처음집 색깔을 미리 정해두고 dp를 구해 나가면 된다. INF = 2147000000 n = int(input()) rgb = [] ans = INF for _ in range(n): rgb.append(list(map(int.. 2021. 10. 7. [Python] 백준 4811번: 알약 https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 1. 알약 한개짜리를 먹으면 반으로 나누어진다. 2. 각 일수마다 알약 반개의 갯수를 배열에 저장하고 마지막일수에 0이 되는것들이 답이다. dp = [[-1 for _ in range(32)] for _ in range(61)] dp[1][1] = 1 for i in range(2, 61): for j in range(31): if dp[i-1][j] >= 0: dp[i][j+1] = max(0, dp[i][j+.. 2021. 10. 7. [Python] 백준 2056번: 작업 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 1. 위상 정렬이다. 각 노드마다 최소비용을 구하는 dp 문제이다. 2. 이전 노드들 중에 가장 큰 비용을 현재 노드의 비용과 더해간다. 3. dp 중에 가장 큰 값이 ans다 n = int(input()) dp = [0 for _ in range(n+1)] graph = [[] for _ in range(n+1)] for i in range(1, n+1): cost, m, *lst = .. 2021. 10. 6. 이전 1 ··· 3 4 5 6 7 8 9 ··· 15 다음