궤도

문제 풀이 이 문제를 풀기 위해선 2차원 dp배열을 사용해야 한다. dp[i][j]를 0부터 j까지의 정수 i개를 더해서 그 합이 j가 되는 경우의 수라고 하자. 쉽게하기 위해 N=4, K=3이라고 하자. 0 1 2 3 4 1 1 1 1 1 1 2 1 3 1 먼저 K=1인 경우 dp[1][j]=1일 것이다. 0부터 j까지의 정수 1개를 더해서 그 합이 j가 되는 경우의 수는 j 스스로를 사용하는 경우 1개 뿐이기 때문이다. 다음으로 N=0인 경우 dp[i][0]=1일 것이다. 몇개의 숫자를 사용한들 그 합이 0이 되기 위해선 0만을 i개 더하는 경우 1개 뿐이기 때문이다. 그렇다면 K=2, N=1인 경우를 보자. 0부터 1까지의 정수 2개를 더해서 그 합이 1이 되어야 한다. 그 합을 a+b+c+d+e...

문제 풀이 myunji.tistory.com/319?category=1154147 [백준] 11052번 : 카드 구매하기 문제 풀이 문제를 풀고 다른 이들의 코드를 찾아봤는데, 다들 범위처리를 나와 다르게 했다. 근데 내가 더 효율적인 것 같고...이렇게 해도 될 것 같기도 하고 그리고 일단 AC를 받았기 때문에 내 myunji.tistory.com 이 문제랑 결이 비슷한 것같다. 32를 제곱수의 합으로 나타낸다고 해보자. 일단 6^2 = 36으로 32보다 크기때문에 6을 쓸 순 없다. 그럼 5^2을 쓰면? 32-25니까 7이 남는다. 예제 입력 1을 보면 알겠지만 7을 표현하는 제곱수 항의 최소 개수는 4다. 그렇기 때문에 5^2를 사용하면 4+1 = 5가 될 것이다. 4^2를 써보도록 하겠다. 32-..

문제 풀이 myunji.tistory.com/217 [백준] 1912번 : 연속합 문제 풀이 이것도 유명한 동적계획법 문제인데... 그냥 뭐 간단하게 생각해서 이런 수열이 있다고 하자 5, -8, 9, -1, ... 당연히 처음은 0으로 시작할 것이다. 0+5를 해서 5가 나왔고 다음 숫자를 보니 myunji.tistory.com 이 문제에서 숫자를 하나 삭제할 수 있게 됐다. 그래서 del_sum이란 변수를 하나 추가한다. del_sum은 숫자를 삭제했을 수도 아닐 수도 있다. 특정 input이 들어왔을 때 del_sum에 들어올 수 있는 경우는 2가지다. 이 input을 사용하거나 삭제하거나. input을 사용할 때는 del_sum = del_sum+input이다. input을 버릴 땐 del_sum..

문제 풀이 내가 원래 LIS를 풀던 방식으로 풀려다가 엄청난 삽질을 했다. myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 이게 내가 원래 LIS를 풀던 방식... 이 문제에선 dp에 최장 길이를 저장할 필요가 없다. 우리가 찾는건 가장 큰 수열의 합이기 때문이다. 그래서 O(n^2)의 시간복잡도로 진행을 할 것이다. 말로 설명하면 어려우니 데이터로 설명하겠다. 1 100 2 50 20 60 3 5 의 데..

문제 풀이 난이도는 플레티넘이지만 이전에 푼 2문제를 합치면 쉽게 풀 수 있어서 풀었다. myunji.tistory.com/324?category=1154147 [백준] 14002번 : 가장 긴 증가하는 부분 수열 4 문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다 myunji.tistory.com 이 문제에서 수열을 출력해보았고 myunji.tistory.com/270 [백준] 12015번 : 가장 긴 증가하는 부분 수열 2 문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가..

문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 단순히 수열의 길이만 구하던 위 문제에서 응용된 문제이다. 처음에는 그냥 length가 늘어날 때마다 dp 배열을 그대로 복사하면 되는거 아닌가? 했다가 반례를 만났다. 10 3 7 4 1 8 이 경우 11053에서 작성한 내 코드 기준 dp를 그대로 복사해오면 1 4 8이란 결과가 나온다. 딱봐도 말도 안된다는 것을 알 수 있다. 그래서 배열의 ..

문제 풀이 문제의 조건에 따르면 스티커를 뗼 수 있는 방법은 OXOX XOXO XOXO OXOX 이렇게 지그재그로 떼는 방법밖에 없다. XXOX XXXX 만약 이 동그라미로 표시한 스티커를 떼고 싶다고 하자. 그럼 그 이전까지의 스티커는 어떤 상태여야 할까? OXOX XXOX XOXX OXXX 이런 모습이어야 할 것이다. 그니까 연속으로 떼거나, 한 칸 건너뛰고 떼거나의 방법이 있는 것이다. 점화식을 작성하면 dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + cost[0][i]; dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + cost[1][i]; 이렇게 된다. dp[0][i]와 dp[1][i]중 더 큰 값이 스티커 점수의 최댓값이다. 소스코..

문제 풀이 myunji.tistory.com/318?category=1154147 [백준] 15988번 : 1, 2, 3 더하기 3 문제 풀이 myunji.tistory.com/298 [백준] 9095번 : 1, 2, 3 더하기 문제 풀이 dp로 풀면 더 빠르겠지만 난 그냥 백트래킹으로 풀었다. 3~1을 빼서 음수가 되지 않으면 계속 빼주면서 백트래킹 재귀 함수를 호 myunji.tistory.com 이 문제에서 숫자의 연속 등장을 제외해야 하는 문제이다. 숫자의 연속 등장을 제외하기 위해선 마지막에 등장한 숫자가 무엇인지 저장해야 한다. 1, 2, 3 더하기니까 마지막에 등장할 수 있는 숫자 역시 1, 2, 3이다. dp[i][j]에 숫자 i를 1, 2, 3의 합으로 나타낸 경우 중 j+1로 끝나는 것..