문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 예시의 수열 10 20 10 30 20 50은 다음과 같이 가장 긴 증가하는 부분 수열을 찾을 수 있다. 앞의 수열에서 작은 수가 있는지 카운트하여, 각 값에 따라 증가하는 부분수열의 길이를 찾을 수 있다. 20 보다 작은 수가 있는가? 수열 10 20 10 30 20 50 카운트 1 2 1 1 1 1 10은 20 보다 작으므로 10의 카운트 값에서 + 1한 값을 20의..
문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀이 자리 수의 증가에 따라 다음과 같은 경우의 수를 확인할 수 있다. 자리 수 1 2 3 4 5 1 10 101 1000 10000 100 1001 10001 1010 10010 10100 10101 즉, N에 따라 만족하는 이친수의 경우는 f(n) = f(n - 1) + f(n - 2)라는 것을 알 수 있다. 이를 코드로 구현하면 간단히 문제를 해결 할 수 있다. 코드 if __name__ == '__main__': n = int(inp..
문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 수의 길이가 1인 경우에는 1 - 9 까지의 계단수가 있으므로 경우의 수는 9개이다. 수의 길이가 2인 경우에는 다음과 같은 경우의 수들이 있다. 시작 수 1 2 3 4 5 6 7 8 9 10 21 32 43 54 65 76 87 98 23 34 45 56 67 78 89 표를 보면 시작하는 수가 1과 9를 제외하고는 시작 수가 가질 수는 경우의 수는 다음과 같이 코드로 나타낼 수 있다. cur = [ cur[1], cur[0] + cur[2], cur[1] + cur[3], cur[2] + cur[4], cur[3] + cur[5], cur[4] + cur[6..
문제 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 풀이 카드 구매하기에서는 구매하고자 하는 카드를 최대값으로 구매하는 문제였다. 이와 달리 카드 구매하기 2는 가장 최소 값으로 카드를 구매할 경우에 발생하는 금액을 반환하는 문제이다. 카드 구매하기와 동일한 방법으로 풀며, 약간의 코드를 수정하면 이 문제도 쉽게 풀 수 있다. 코드 if __name__ == '__main__': N = int(input()) card = [0] + list(map(int, input().split())) memo = [0]..
