[백준] 14002번 (python 파이썬)
https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 11053번과 비슷한 문제이다. 11053번 문제를 풀 수 있어야 이 문제도 풀 수 있다. HTML 삽입 미리보기할 수 없는 소스 두 문제의 차이점으로는 11053번은 길이를 출력했지만, 이 문제는 길이 뿐 아니라 LIS 그 자체도 출력해야 한다. 11053번의 경우는 길이를 출력하기위해 길이정보를 메모이제이션을 했..
[백준] 11053번 (python 파이썬)
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 LIS 라는 유명한 문제라고 한다. 처음 이 문제를 읽고 DP가 왜 필요하지? 생각했다. 맨 처음수를 temp에 넣고 다음 수와 비교하면서 큰수가 나오면 바꿔치기 하고 count하면 될 줄 알았다. 즉, 1, 3, 5, 4, 6라는 수열이 있다면 1을 temp에 넣고 3과 비교, temp에 3을 넣고 coun..
[백준] 15990번 (python 파이썬)
https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net import sys testcase = int(input()) cache = [[0 for _ in range(4)] for i in range(100001)] cache[1] = [0,1,0,0] cache[2] = [0,0,1,0] cache[3] = [0,1,1,1] for i in range(4, 100001): cache[i][1] = (cache[i-1][2] + cache[i-1][3]) cache[i][2] = (cache[i-2][..
