For Programmer

import sys input = sys.stdin.readline N = int(input()) cost = [[0, 0, 0]] for _ in range(N): cost.append(list(map(int, input().split()))) dp = [i for i in cost] for i in range(2, N + 1): dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + dp[i][0] dp[i][1] = min(dp[i - 1][2], dp[i - 1][0]) + dp[i][1] dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + dp[i][2] print(min(dp[N])) -> 간단한 문제이다. dp를 우선 입력받은 cost와 ..

위 문제도 역시 파이썬의 itertools.product 내장 함수를 이용하여 K개씩 뽑아서 그합이 N과 같으면 개수를 더하는 식으로 풀어봤으나 역시나 시간초과가 발생했다. 그렇다면 역시 DP문제이기에 조건을 찾아야 한다. N이 1일때부터~쭉 K가 1일때부터 해서 2차원 표와 같이 그려보면 다음과 같은 그림이 나온다. 먼저 그림을 보고 설명을 하겠다. n = 1 n = 2 n = 3 n = 4 n = 5 k = 1 1 1 1 1 1 ... k = 2 2 3 4 5 6 ... k = 3 3 6 10 15 21 ... N과 K의 관계에 대해 생각해보자. N이 1일때는 무조건 K가 1씩 증가한다. ex) k = 2 이고 n = 1 이면 (0, 1) (1, 0) 2개 ex) k = 4 이고 n = 1 이면 (0..

이 문제는 우선 개수를 쭉 구해보고 규칙이 있는지 찾아봐야 한다. 0 - 0개 1 - 1^2 (1개) 2 - 1^2 + 1^2 (2개) 3 - 1^2 + 1^2 + 1^2 (3개) 4 - 2^2 (1개) 5 - 2^2 + 1^2 (2개) 6 - 2^2 + 1^2 + 1^2 (3개) 7 - 2^2 + 1^2 + 1^2 + 1^2 (4개) 8 - 2^2 + 2^2 (2개) 9 - 3^2 (1개) 10 - 3^2 + 1^2 (2개) 11 - 3^2 + 1^2 + 1^2 (3개) 12 - 2^2 + 2^2 + 2^2 (3개) 13 - 3^2 + 2^2 (2개) 14 - 3^2 + 2^2 + 1^2 (3개) 15 - 3^2 + 2^2 + 1^2 + 1^2 (4개) 16 - 4^2 (1개) 와 같이 나온다. 여기서..

N = int(input()) input_array = list(map(int, input().split())) dp = [input_array[0]] * N for i in range(1, N): dp[i] = max(dp[i - 1] + input_array[i], input_array[i]) print(max(dp)) ->원리는 간단하다. 기존 dp문제처럼 최댓값을 계속 dp배열에 넣어서 새로운항이 나오면 전에 저장되어있던 최댓값에서 그 새로운항의 값을 더한 값이 기존의 최댓값보다 크다면 그값을 저장해주면 되는 방식이다. 이문제는 간단하면서도 어렵지 않은 문제인데도 불구하고 정답률이 낮은것을 보고 쉽게 생각하지 못해 이중반복문으로 풀려고 해서 계속 시간초과가 발생했다. ㅠ

이 문제는 11053번(https://ji-gwang.tistory.com/277) 과 굉장히 비슷하지만 한가지 더 추가되었다. 가장 긴 증가하는 부분 수열을 길이와 함께 같이 출력하라고 한다. 어떻게 접근하면 될까? 많은 시도를 해보던 중 한가지를 발견했다. 11053번의 해설에서 dp에 저장 되어 있는 값을 잘 보면 해당 값들은 현재 배열에서 앞 원소들보다 몇번째로 큰 지에 대한 순서를 나타내준다. 예를들어 1 3 2 라는 값을 입력한다면 dp에는 [1,2,2] 가 저장이 된다. 그렇다면 1은 1번째, 3과 2는 2번째라는 것을 알 수 있다. 또한 문제에서 입력처럼 10 20 10 30 20 50 을 입력한다면 dp에는 [1,2,1,3,2,4]가 저장 된다. 50은 4번째 30은 3번째 20은 2번째..

위의 문제는 최장 증가 부분 수열(LIS) 알고리즘 이라고 실제로 존재하는 알고리즘이다. 위의 알고리즘은 간단히 얘기하면 입력받은 배열 원소에 하나씩 접근하여 뽑은 원소 직전에 존재하는 원소들과 일일이 하나씩 크기를 비교하며 만약 작은 값이 존재하면 DP에 부분수열값을 +1 씩 해주는 알고리즘이다. 말로설명하면 어려우니 코드를 한번 보면 이해하기 쉽다. N = int(input()) input_array = list(map(int, input().split())) dp = [1] * N # 최장수열 길이를 저장할 dp 리스트선언 for i in range(N): # 배열 길이만큼돈다. for j in range(i): # 해당 배열 원소의 직전 원소까지 돈다. if input_array[i] > inpu..

위 문제도 DP문제 이기에 점화식만 찾으면 쉽게 해결할 수 있는 문제이다. 다음을 보면 N이 1~6 일때의 이친수들을 보여주는데 개수의 증가가 1-1-2-3-5-8... 이런식으로 증가하기 때문에 피보나치 수열이라는 것을 알 수 있다. 1 2 3 4 5 6 1 1 10 100 10000 10000 100000 2 101 1010 10100 101000 3 1001 10010 100100 4 10001 100010 5 10101 101010 6 100001 7 101001 8 100101 N = int(input()) dp = [1 for _ in range(N + 1)] for i in range(3, N + 1): dp[i] = dp[i - 2] + dp[i - 1] print(dp[N])

해당 문제는 다음과 같은 방법으로 접근할 수 있어야 한다. 1. dp를 이차원 배열로 설정한다. 2. 이차원 배열중 행은 N(자리수) 열은 맨뒷자리에 오는수(10이라면0 231이라면 1) 라고 생각을 해야한다 (dp[자리수][맨뒤에오는수]) 3. 맨 앞자리가 0일때는 횟수를 세지 않는다. 4. 1~8일때는 전에 자리수에서 -1,+1 일때의 횟수를 더해주면된다. (ex) 2일때는 1일때와 3일때의 횟수에서 두개를 더해준값이다. 왜냐하면 12 or 32 으로 맨뒤에 2가 올 수 있는 경우의 수이기 때문이다. 5. 9일때는 8밖에 올 수 없다. 즉, 89xxx... 밖에 될 수 없기 때문이다. 정리하자면 N=1일때 dp[1][0] = 0 , dp[1][1] ~ dp[1][9] = 1 N=2일때 dp[2][0]..