viamemine

문제: https://www.acmicpc.net/problem/1912  풀이이번 문제는 연속 합의 최댓값을 구하는 문제입니다. 선택을 하냐, 하지 않느냐에 따라 dp[i]가 채워집니다. 어려운 문제는 아니였기 때문에 점화식을 구해서 풀 수 있었습니다.이전 값(dp[i-1])에 이번 값(arr[i])를 더한 값을 0과 비교해서, 최댓값을 dp[i]에 채우도록 풀었습니다.   n = int(input())arr = [0] + list(map(int, input().split()))dp = [0] * (n+1)if max(arr[1:])

문제: https://www.acmicpc.net/problem/2579 풀이오늘 문제는 경우의 수를 나누어 풀어야 하는 문제로, 점화식을 찾는데 어려움이 있었습니다.i를 점수 계산으로, j를 0/1/2번 연속 밟을 때로 간주하여 문제를 해결했습니다. 따라서, dp[i][j]는 i번 계단을 j번 연속 밟았을 때의 최대점수를 의미합니다. 그림을 보면서 설명드리겠습니다. dp[0]일 때, j = 0, 1, 2는 초기값 0입니다.  dp[1]일 때, j = 0은 계단을 밟지 않은 경우로 초기값 0입니다. dp[1]일 때, j = 1은 계단을 1번 밟은 경우로 10 입니다.dp[1]일 때, j = 2는 계단을 연속 2번 밟은 경우이지만 첫번째 계단이기 때문에 2번 밟을 수 없고, 10 입니다.  dp[2]일 때..

문제: https://www.acmicpc.net/problem/11726 풀이  계속해서 dp문제를 풀고 있습니다. 앞서 다른 게시글에서도 말씀드렸듯이, dp는 점화식을 구하는게 문제 해결의 핵심입니다 ! 아래의 그림처럼 n이 1일 때부터차근차근 경우의 수를 생각해보시면 점화식을 구할 수 있습니다. 아, 저는 dp를 (n+1)만큼만 구해서 답을 출력하려고 했으나 index error가 나오더라구요. n이 1이거나 2일 때, error가 발생하기 때문입니다. 따라서 dp는 문제와 같이 1000까지 구해야 오류 없이 정답을 도출할 수 있습니다.    n = int(input())dp = [0 for _ in range(10000)] # (n+1)만큼 하면 index errordp[1] = 1dp[2] = ..

문제: https://www.acmicpc.net/problem/9095 풀이 이번 문제도 DP 문제입니다.DP의 핵심은 점화식을 찾는 것인데, 쉽사리 점화식이 잘 보이지 않았던 문제입니다. 하지만 여러 문제를 풀어보고 나니, '1, 2, 3' 이게 하나의 힌트가 될 수 있음을 알게되었습니다.  오늘도 문제 풀이의 과정은 이해가 쉽도록 그림을 첨부하겠습니다 !   위의 그림처럼 n이 1일 때, 2일 때, 3일 때이렇게 순차적으로 정답을 생각해보면 좋습니다. n이 4일 때는 (n이 3인 경우 + 1), (n이 2인 경우 + 2), (n이 1인 경우 + 3) 임을 알게되었습니다.이렇게 점화식을 찾았으면, 코드를 작성하는 건 어렵지 않습니다 ^.^ !  코딩 고수가 되고싶네요 ...자 이제 코드를 보겠습니다 ..

문제: https://www.acmicpc.net/problem/1463  풀이  dp는 점화식을 찾는 것이 문제 풀이의 핵심입니다. -1, /2, /3의 방법으로 점화식을 찾으려고 노력했는데요. 예를 들어, 그림과 같이 6을 구하는 횟수를 구할 때,1만큼 작은 5보다는 1회 증가하고 (+1하면 되니까)2로 나눈 3보다도 1회 (*3 하면 되니까),3으로 나눈 2보다도 1회(*2 하면 되니까) 증가합니다. 이렇게 점화식을 찾았으며, 코드로 구현하면 다음과 같습니다.   x = int(input())dp = [0] * (x+1) # 계산된 결과를 저장하기 위한 DP 테이블 초기화for i in range(2, x+1): # 보텀업 dp[i] = dp[i-1] + 1 # 현재의 수에서 1을 빼는 경우 ..