No regret Just Lesson

풀이 data 10 20 10 30 20 50 dp 1 2 1 3 2 4 dp 문제입니다. data 변수에는 입력값을, dp 변수에는 현재 위치에서 최대 길이를 저장합니다. dp변수는 기본적으로 자신의 길이 1을 가지므로 1로 초기화 해줍니다. dp 변수에는 현재 데이터보다 값이 작은 이전 데이터들 중에서 최대 dp값에 1을 더하여 저장합니다. 출력 시에는 dp의 마지막 원소가 최댓값이라는 보장이 없기 때문에 dp에서 최댓값을 뽑아 출력합니다. Python3 Code import sys n = int(input()) data = list(map(int, input().split())) dp = [1] * n for i in range(1, n): max_dp = 0 for j in range(0, i):..

풀이 DP 문제입니다. 1번째에는 무조건 1이 오고 2번째부터 0과 1이 나올 수 있는데 1이 두 번 연속으로만 나오지 않으면 됩니다. dp 변수에 현재 위치가 0일 때와 1일 때의 경우의 수를 각각 저장할 것입니다. 현재 위치가 0이라면 이전 자리는 0, 1 두 가지 모두 올 수 있습니다. 따라서 dp [i][0] = dp [i-1][0] + dp [i-1][1] 이 됩니다. 현재 위치가 1이라면 이전 자리는 무조건 0이어야 합니다. 따라서 dp [i][1] = dp [i-1][0] 이 됩니다. 출력으로는 현재 위치가 0인 경우의 수와 현재 위치가 1인 경우의 수를 더하여 출력하면 됩니다. 변수 dp [i][0] = i자리에서 0인 경우의 수 dp [i][1] = i자리에서 1인 경우의 수 Python..

풀이 DP 문제이다. 입력 데이터를 처음부터 살펴보면서 선택의 최댓값을 찾을 것이다. 문제 조건에서 3번 연속으로 포도 잔을 선택할 수 없기 때문에 다음과 같은 경우를 생각해본다. 현재가 0번 연속, 즉 i-2, i-1번이 선택되었다 현재가 1번 연속, 즉 i-2, i 번이 선택되었다 현재가 2번 연속, 즉 i-1, i 번이 선택되었다 변수 설명 data : i 번째 입력 값 dp : i 번째 최댓값 Python3 Code import sys n = int(sys.stdin.readline()) data = [0] + [int(sys.stdin.readline()) for _ in range(n)] + [0] dp = [0] * (n+2) # i번째 최댓값 dp[1], dp[2] = data[1], da..

풀이 기본적인 DP 문제이다. 작은 수의 계산 결과를 저장하면서 다음 문제를 해결할 때 이용하면 간편하게 문제를 해결할 수 있다. 입력과 출력을 한번 생각해보자. 입력이 1이라면 답은 0, 입력이 2라면 답은 1이다. 입력이 4라면 2로 한번 나눠서 2가 될 것이고 2를 1로 만드는 연산 횟수는 먼저 계산했듯 1이다. 입력이 16이 들어온 경우 만약 8을 1로 만드는 최소 횟수를 안다면 그것에 1만 더하면 된다. 입출력의 예시를 생각해보면, 작은 숫자를 1로 만드는 연산 횟수를 알고 있다면 더 큰 수일 때 이 문제를 푸는 핵심은 문제를 최대한 분해한 다음 가장 작은 수에서부터 그것을 1로 만드는 연산 횟수를 구하는 것이다. 소스코드에서 n%2, n%3을 더해주는 것은 해당 숫자로 나누어지지 않았을 때 1..