알고리즘/동적프로그래밍(DP)42

• 

  [Python] 백준 11057번: 오르막 수 풀이 소스코드 n = int(input()) # dp 초기화 (최소 1개는 있으므로) #dp[i][j] 에서 i는 자리수, j는 끝에 오는 수 dp = [[0]*10 for _ in range(n+1)] dp[1] = [1]*10 for i in range (1, n+1): for j in range (0, 10): for k in range (0, j+1): dp[i][j] += dp[i-1][k] print(sum(dp[n]) % 10007) 저번 문제와 마찬가지로 자리수에 따른 끝 자리 숫자로 규칙을 유추하였다. 1자리 일 때는 당연히 모든 숫자가 1가지 방법을 가진다. (0도 숫자 첫번째에 올 수 있음) 2자리 일 때는 _0 은 1개, _1은 2개, _2는 3개, ...._9는 10개를 가진다. 3자리.. 알고리즘/동적프로그래밍(DP) 2021. 1. 21.

• 

  [Python] 백준 10844번: 쉬운 계단 수 풀이 소스코드 n = int(input()) # dp 초기화 (최소 1개는 있으므로) dp = [[1]*10 for _ in range(n+1)] # dp[i][j] 에서 i은 자리수, j는 수의 마지막 숫자 # 1자리 수는 0이 끝에 올 수 없으므로 0개로 저장 dp[1][0] = 0 if n!= 1 : for i in range(2, n+1): for j in range(0, 10): if j==0 : dp[i][j] = dp[i-1][1] elif j==9 : dp[i][j] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[n]) % 1000000000) dp채우기/ dp[i][j] / i는 자리수, j는 수의 끝에 오는 숫자.. 알고리즘/동적프로그래밍(DP) 2021. 1. 21.

• 

  [Python] 백준 9095번: 1, 2, 3 더하기 풀이 소스코드 T = int(input()) for i in range(T): dp = [0,1,2,4] n = int(input()) for j in range(4,n+1): dp.append(dp[j-3] + dp[j-2] + dp[j-1]) print(dp[n]) 0 -> 0개 1 = 1 -> 1개 2 = 1 +1 -> 2개 = 2 3 = 1 + 2 -> 4개 = 2 + 1 = 3 = 1 + 1 + 1 까지는 쉽게 구할 수 있다. 그렇다면 4는? 크게 세 가지 방법으로 1 + 3 / 2 + 2 / 3 + 1 이 있다. 왜냐면 1,2,3의 합으로 표시를 하는 것이므로 항상 1 + (n-1) / 2 + (n-2) / 3 + (n-3) 으로 구할 수 있는 것이다!! 그렇다면 밑줄 친 3, 2, 1 을 또 여러.. 알고리즘/동적프로그래밍(DP) 2021. 1. 21.

• 

  [Python] 백준 11727: 2xn 타일링 2 풀이 소스코드 n = int(input()) dp = [0,1,3] for i in range(3,n+1): dp.append(2 * dp[i-2] + dp[i-1]) print(dp[n] % 10007) 저번 문제와 동일한 구조이다. 이번에는 2x2 타일이 추가되었으므로, dp[n-2] 에서 dp[n] 이 되기 위해선 1x2 타일 2개를 놓는 방법, 2x2 타일 1개를 놓는 방법 -> 2 * dp[n-2] 의 횟수와 동일 + dp[n-1] 에서 dp[n] 이 되기 위해서 2x1 타일 1개를 놓는 방법 -> dp[n-1] 의 횟수를 더해주면 된다. 즉, dp[n] = 2 * dp[n-2] + dp[n-1] 로직이 거의 동일하여 더 이상의 설명은 생략하겠다. 자세한 설명은 11276 참고! 알고리즘/동적프로그래밍(DP) 2021. 1. 20.

• 

  [Python] 백준 11726번: 2xn 타일링 풀이 소스코드 n = int(input()) dp = [0,1,2] for i in range(3,n+1): dp.append(dp[i-2] + dp[i-1]) print(dp[n] % 10007) 처음에는 감을 못 잡았는데 n의 갯수를 1부터 5까지 늘려가면서 규칙을 파악했다. n=1 -> 1 n=2 -> 2 n=3 -> 3 n=4 -> 5 n=5 -> 8 즉, 피보나치와 같은 관계식을 이끌어 낼 수 있다. dp[n] = dp[n-2] + dp[n-1] 어거지로 규칙을 알아냈긴 했는데, 왜 이렇게 되는지 생각을 해보자. 1) 2*(n-1) 에서 2xn 개로 늘리려면, 2x1 개의 타일밖에 사용하지 못한다. -> 언제나 저 방법밖에 존재하지 않으므로 이 경우에는 dp[n-1] 의 방법 개수와 같다. 즉, 검정.. 알고리즘/동적프로그래밍(DP) 2021. 1. 20.

• 

  [Python] 백준 1463: 1로 만들기 풀이 소스코드 n = int(input()) #인덱스와 일치하는 정수를 1로 만들기 위한 횟수의 최솟값 dp = [0,0,1,1] for i in range(4,n+1): # 1을 만들기까지 최대 횟수로 초기 dp.append(i-1) # 1을 뺄 때의 최솟값 dp[i] = dp[i-1] + 1 # 2로 나누어 떨어질 때 if i % 2 == 0 : # 1을 뺄 때와 2로 나눌 때 더 작은 횟수인 것을 저장 dp[i] = min(dp[i], dp[i//2] + 1) if i % 3 == 0 : # 앞에서 구한 arr[i]과 3으로 나눌 때 더 작은 횟수인 것을 저장 dp[i] = min(dp[i], dp[i//3] + 1) print(dp[n]) 처음 풀어보는 DP 문제라 조금 당황하긴 했다. 그래서 처음엔 .. 알고리즘/동적프로그래밍(DP) 2021. 1. 20.