[Python] 백준 알고리즘 온라인 저지 14002 가장 긴 증가하는 부분 수열 4 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번을 풀게 되었다;; 소스코드 import sys i..
[Python] 백준 알고리즘 온라인 저지 2193 이친수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제에 제시된 조건을 만족하는 n을 작은 수부터 계산해보니 쉽게 점화식을 만들 수 있었다. 소스코드 import sys input = sys.stdin.readline n = int(input()) dp = [0, 1, 1] for i in range(3, n+1): dp.append(dp[i-2]+dp[i-1]) print(d..
[Python] 백준 알고리즘 온라인 저지 10844 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제로 증가와 감소 상관없이 1씩 계단식으로 이루어진 수의 경우를 구하는 문제로 0은 제일 앞에 올 수 없다. 쉬운 이라는 타이틀이 무색하게 어려웠다.😅 소스코드 import sys input = sys.stdin.readline n = int(input()) dp = [[0] * 10 for _ in range(n+1)] for i in range(1, 10): dp[1][i] = 1 for i in range(2, n+1): for j..
[Python] 백준 알고리즘 온라인 저지 16194 카드 구매하기 2 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 저번 카드 구매하기 문제에서는 카드 n장을 구매 비용을 최댓값으로 구했다면 이번에는 최솟값을 구하는 문제이다. 코드 import sys input = sys.stdin.readline n = int(input()) p = [0] + list(map(int, input().split())) dp = [False for _ in ra..
[Python] 백준 알고리즘 온라인 저지 11052 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 이번 문제의 핵심은 n장의 카드를 구매하는데 가장 많은 돈(최대 값)을 사용해야 한다는 점이다. 문제를 이해하는 것은 오래 걸리지 않았지만 점화식을 어떤 방식으로 만들어야 하는지 이해하는데 오래 걸렸다. 코드 import sys input = sys.stdin.readline n = int(input()) p = [0] + list(ma..
[Python] 백준 알고리즘 온라인 저지 9095 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제는 1, 2, 3의 합으로 n개의 수들을 나타내는 방법의 수를 묻는 문제이다. DP와 점화식을 이용하여 풀이하는 어렵지 않은 문제였다. 코드 import sys input = sys.stdin.readline n = int(input()) for _ in range(n): a = int(input()) dp = [0, 1, 2, 4, 7] for i in range(5, a+1): dp.append(dp[i-3]+dp[..
🚀 새로운 블로그로 이전했습니다.
살펴보러 가기
