파이문

2293. 동전 1(https://www.acmicpc.net/problem/2293) 동전 경우의 수 구하는, 나름 유명한 문제다. 역시나 알고스팟에도 같은 문제가 있다. (https://algospot.com/judge/problem/read/COINS) 구하려는 값 크기를 갖는 배열 dp를 만드는 데, 이 때 사이즈를 값 + 1 해야, 예외 처리 따로 하지 않고 쉽게 할 수 있다.이렇게 만들어진 dp 에 경우의 수를 갱신하는데, i는 i원을 의미한다. 예를 들어서 dp[3]은 3원을 만드는 방법인데, 3원을 만드는 방법은 1원을 만드는 방법과 2원을 만드는 방법 두개를 더 하면 된다. 유투브에 강의 몇 개가 있어서 하나 첨부해 본다. https://www.youtube.com/watch?v=jaNZ..

11053. 가장 긴 증가하는 부분 수열(https://www.acmicpc.net/problem/11053) 유명한 문제이다. (알고스팟에도 있는 문제다. https://algospot.com/judge/problem/read/LIS) 일명 Longest Increasing Sequence 라는 문제인데, 주어진 수열에서 가장 긴 길이를 가질 수 있는 증가하는 부분 수열의 길이를 리턴해야 한다. 가장 먼저 1로 (가질 수 있는 최소 길이값이 길이1이므로) 값을 초기화 한 dp를 선언하고, i는 1부터 길이까지 증가시키고 j는 0부터 i까지 증가 시켜서, i번째 값이 j번째 값 보다 크면 dp[j] + 1이나 현재 값 dp[i] 중 maximum 값으로 갱신하는 것이다. 동영상 설명이 잘 되어 있어서 링..

2579. 계단 오르기(https://www.acmicpc.net/problem/2579) 문제의 요점은 연속해서 계단 3개를 밟을 수 없다는 것이다. 작은 단위로 계단이 3개 있을 때를 가정하자면 다음과 같다.1번 계단 -> 3번 계단 과 1번 계단 -> 3번 계단을 밟는 것 중 최대 값이 3번째 계단에 다다랐을 때의 최대 값이 되는 것이다. (문제에서는 무조건 마지막 계단을 밟아야 한다.) 계단이 4개 있을 때로 문제를 늘리면 1. 1번 계단 -> 3번 계단 -> 4번 계단 (dp[1] + 계단[3] + 계단[4])2. 1번 계단 -> 2번 계단 -> 4번 계단 (dp[2] + 계단[4]) 왜 1번 계단 이 dp[1]이 되고 1번 계단 -> 2번 계단이 dp[2]가 되는지는, 계단 수를 늘려서 그려보..