남남이루의 고군분투 🌳

문제 풀이 프로세스 (오답) 1. 문제의 주요 변수들 명시 2. DP의 빈배열이 있다고 가정하고, 문제의 조건에 맞는 답을 나열해보기 3. 나열한 것들 중에서 규칙찾기 # n 개의 물건, 최대 100개 # k 가용 무게 # w 무게와 v 가치 더보기 y = 무게 d[x][y] = 가치 총합? d[x][0] = 0 d[x][1] = 0 d[x][2] = 0 d[x][3] = 6 d[x][4] = 8 => max(d[x][3], d[x][4]) d[x][5] = 12 => max(d[x][4], d[x][5]) d[x][6] = 13 => max(d[x][5], d[x][6]) d[x][7] = 14 => max(d[x][6], d[x][3]+d[x][4]) # 이중 포문으로 탐색할 부분 d[무게] = 가치..

d = [[0]*10 for _ in range(n+1)] # d[x][y] # x = 자리수 # y = 앞에오는 숫자? # d[2][2] = d[1][1] + d[1][3] # d[3][2] = d[2][1] + d[2][3] for k in range(1,10): d[1][k] = 1 for i in range(2,n+1): for j in range(10): if j == 0: d[i][j] = d[i-1][1] elif j == 9: d[i][j] = d[i-1][8] else: d[i][j] = d[i-1][j-1] + d[i-1][j+1] mod = 1000000000 print(sum(d[n]) % mod)

이항계수를 구하는 문제 n과 k 가 주어질 때, 두 수에 해당하는 이항계수를 구하는 것이 문제이다. 관건은 이항계수의 개념을 알고, 이를 코드로 구현하는 것이다. (단, 수의 범위가 1,000으로 그렇게 크지 않기 때문에 전체 숫자를 구한 다음에 접근하는 방법도 가능하다.) 이항계수 이해하기 조합론에서, 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다. 위의 이항계수 주요성질을 참고해, 코드를 구현할 수 있다. 정의식 (n)! / (n-k)!(k)! 을 이용하거나, 1 또는 2를 이용해 재귀함수나 dp를 사용한 코드를 볼 수 있다. (맨 밑 참고 블로그 확인) 아래의 코드는 botto..

10844 쉬운 계단 문제를 풀면 dp 배열을 2차열로 활용하는 게 나온다. 이 원리를 그대로 적용할 수 있겠다 싶었다. 자리수에 대한 관계를 점화식으로 표현할 수 있다는 게 공통점이었기 때문이다. import sys input = sys.stdin.readline l = int(input()) d = [[0]*10 for _ in range(l+1)] for k in range(10): d[1][k] = 1 for i in range(2,l+1): for j in range(10): d[i][j] = sum(d[i-1][j:]) print(sum(d[l])%10007) sum을 두 번 쓰는 게 낯설었는데, 나열해보면 그 이유를 알 수 있었다. # d[2][0] # d[2][4] = d[1][4::-1]..

주어진 동전들로 k원 금액을 만들어라! 틀린 이유 1. for 문 구현에서 index랑 범위 설정이 이해가 잘 안 갔었다.

와 미챠따.. 첨으로 답안보고 풀었다 관건은, d[x]가 최대금액을 보장하는 놈이 들어있고, 카드팩을 돌면서 비교하면 됨. 규칙을 찾기 위해 적어보자면, p[x] = y x 카드 갯수 y 금액 d[1] = p[1] d[2] = max(p[1], p[2]) d[3] = max(p[1]+p[2], ) d[4] = max(d[3]+p[1], d[2]+p[2]) d[5] = max(d[4]+p[1], d[3]+p[2]) max안에 들어갈 내용들만 봤을 때, d와 p의 인덱스들의 합이 d의 인덱스임을 알 수 있었음 import sys input = sys.stdin.readline n = int(input()) d = [0] * 1001 p = [0] +list(map(int, input().split())) f..

바텀업으로 배열을 채우고, 인덱스 n에 해당하는 값을 출력하는 식으로 품 d의 기본 배열을 각 인덱스로 채우는 게 다른 DP문제랑 다른 점이었고, ( 1**2로만 더한 횟수가 최대이므로, 3 = 1**2 + 1**2 + 1**2 , 3에 대해 최대 횟수가 3임 ) 이중 반복문, 제곱근까지는 생각했는데, 이걸 식으로 구현하는 게 어려웠다. 뺄셈으로 해결하신 분의 코드를 참고했다. 11을 예시로 원리를 설명해보자면, 11은 제곱의 항들로 표현되는 가짓수들의 일부는 이렇다. 11 = 1**2 + 1**2 + ... 11 = 2**2 + 2**2 + 1**1 + 1**1 + 1** 1 11 = 3**2 + 1**2 + 1**2 (최소 횟수) 어떤 자연수 N에 대해, N=1부터 시작하면서 N보다 작은 제곱수를 가..

풀이 과정 1. 점화식으로 표현해보기 2. 작은 수부터 일일이 계산해 규칙 찾아내기 3. 바텀업으로 풀어보기 >>> 런타임 에러 4. 생략된 규칙 추가하기 (%15746) >>> 메모리 초과 5. %15746의 위치를 출력 구문이 아닌, 입력 부분으로 옮김 >>> 런타임 에러 ------ 계속해서 index 에러가 나고 있었다. 다른 분들의 코드를 참고한 결과, 가장 큰 차이점은 빈 배열을 만드는 부분이었따. 나는 d = [0] * (n+1)로 했는데, 다른 사람들은 아예 배열의 길이를 N의 최대값인 1000000+1로 고정해뒀더라. 그걸 수정하니, 정답처리 되었다. 아직 왜 그런지는 모르겠다. import sys input = sys.stdin.readline n = int(input()) d = [0..

문제 요구사항 정수 X를 1로 만들기 위한 연산이 3가지가 있다. 이를 적절히 사용하여 1로 만들고자 할 때, 최소한의 연산 횟수를 구하라 주의사항과 DP의 특징 어떤 N에 대해 나올 수 있는 모든 연산의 횟수를 구하면, 이 문제는 시간초과가 뜬다. N보다 작거나 N을 2나 3으로 나눴을 때의 small N들이 최소한의 연산횟수로 도출된 것을 이용해 N의 최소연산횟수를 구하게 되면, 훨씬 시간자원을 아낄 수 있다. small N들은 문제에서 제시한 연산 방법에 따라 2나 3을 나눈 수, -1을 한 수들이다. 예를 들어 6의 최소연산횟수를 구하고자 할 때, N = 6이고, small N들은 2,3,5가 된다. 2,3,5를 만들 때 사용했던 연산에 각각 *3, *2, +1을 하게 되면 6을 만들 수 있으므로..

DP란, 피보나치처럼 작은 문제로 분할하여 현재의 값을 구하는 문제에 대해 메모리 공간을 활용함으로써 속도를 비약적으로 줄이는 기법이다. 점화식으로 표현되는 문제들을 DP기법을 활용할 경우 효율적으로 답을 구할 수 있다. 점화식이란, 인접한 항들 사이의 관계식을 의미한다. 예를 들어 수열에서의 각 항을 An이라고 부를때, 우리는 점화식을 이용해 현재의 항을 이전항에 대한 식으로 표현할 수 있다. DP로 해결할 수 있는 가장 대표적인 유형인 피보나치의 점화식은 A(n+2) = A(n+1) + An 으로 표현할 수 있다. 프로그래밍과 점화식 n번째 피보나치수를 f(n)이라고 표현할 때, f(4)를 구하고자 할 때 f(2)와 f(1)은 항상 1이므로 이때는 호출을 정지하는 코드를 넣어 재귀함수로 풀 수 있다...