viamemine

문제: 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을 빼는 경우 ..