https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 다이나믹 프로그래밍 문제.. 점화식 세우는 게 너무 어렵다 dp[i] = max(dp[i-2]+scores[i], dp[i-3]+scores[i-1]+scores[i]) 이게 아니라 dp[i] = max(dp[i-2]+scores[i], dp[i-3]+scores[i-1]+scores[i], dp[i-1]) 가 아닌가?! 하는 오해가 있었는데 (불리하면 현재 계단을 밟지 말아야 한다고 생각해서) 한 번에 2개..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 다이나믹 프로그래밍 문제다. 연속적으로 3잔의 포도주를 먹을 수 없다는 제한이 있다. i번째 포도주에 해당하는 dp값은 i번째 포도주를 마시는 경우와 마시지 않는 경우로 나눌 수 있는데 (1) i번째 포도주를 마시는 경우 (1.1) i-1번째와 i번째 포도주를 마시는 경우: i-2번째는 먹지 못하니까 dp[i-3] + wine[i-1] + wine[i] (1.2) i-1번째 포도주는 마시지 않고 i..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 나누고 빼는 대신 곱하고 더하는 것으로 바꿔 풀었다. N에서 1로 줄여나가는 것이 아니라, 1에서 N으로 늘려가는 것으로 방향을 반대로 보고 풀었다. 먼저 dp를 모두 N인 리스트로 초기화해주고, index 1의 값만 0으로 바꿔준다. 1부터 N-1까지 다음을 반복한다. 현재 i에서 3 곱한 것이 N 이하면, graph[i]+1의 값과 graph[i*3] 중 최솟값 취하기 현재 i에서 2 곱한 것이 N 이하면, graph[i]+1의 값과 graph[i*2] 중 최솟값 취하기 현재 i에서 1 더한 것이 N 이하면..

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net '가장 긴 증가하는 부분 수열(LIS)'을 이용해 풀이했습니다. 이 문제는 오름차순이 아니라 내림차순을 요구하므로, 점화식의 부등호 방향만 바꾸어줬습니다. dp는 모두 1로 초기화하고, soldiers는 입력으로 받은 병사들의 전투력을 저장합니다. 점화식: 모든 0 soldiers[i] 이후 dp의 최댓값을 구하면 가장 긴 내림차순 부분 수열의 길이가 되고, 이를 전체 병사의 수인 N에..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 각 날짜까지의 누적 이익을 담은 dp 리스트를 만들고, 다이나믹 프로그래밍으로 풀이했습니다. 처음엔 모두 0으로 초기화합니다. 입력을 받으면서 start는 현재 일이 시작되는 날, end는 현재 일이 끝나는 날, profit은 현재 일로 얻을 수 있는 이익으로 정의합니다. (현재 일이 시작되기 전까지의 이익 + 현재 일을 끝낸 후의 이익)과 (일이 끝나는 날의 기존 dp 값) 중 큰 값을 dp[end]로 갱신합니다. 이때 end+1일 이후의 누적 이익이 end일까지의 누적 이익보다 적을 수 없으므로 , dp[end+1:]의 모든 값을..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 모든 정수를 거쳐가며 다음을 처리합니다. 첫 행은 아무 계산도 하지 않습니다 2번째 행부터 중간에 위치한 정수들은 직전 행의 오른쪽, 왼쪽 대각선의 수 중 큰 것을 더합니다. 첫 번째에 위치한 정수들은 직전 행의 첫 번째 수를 더합니다. 마지막에 위치한 정수들은 직전 행의 마지막 수를 더합니다. 계산이 끝난 후 마지막 행의 최댓값을 반환합니다. 시간 복잡도: O(N) import sys # 입력 처리하기 nums = [] # 삼각형의 크기 N = int(sys.stdi..