[Python] 백준 알고리즘 온라인 저지 14501 퇴사 출처 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 알고리즘 분류 다이내믹 프로그래밍 브루트포스 알고리즘 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는 데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같..
[Python] 백준 알고리즘 온라인 저지 11057 오르막 수 출처 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 자릿수가 오름차순으로 증가하는 수를 오르막 수라고 하고 이전이나 다음 자릿수는 같은 크기를 가져도 오르막 수이다. 점화식을 찾아 문제를 풀이해야 했고 그 과정이 생각보다 오래 걸렸다. N과 끝으로 오는 수를 기준으로 점화식을 세워야 한다. 알고리즘 분류 다이내믹 프로그래밍 소스코드 import..
[Python] 백준 알고리즘 온라인 저지 1309 동물원 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 이번 문제도 다이내믹 프로그래밍을 이용해 경우의 수를 계산하는 문제로 주의할 점은 사자가 없는 경우도 경우의 수로 계산한다는 점이었다. 알고리즘 분류 다이내믹 프로그래밍 소스코드 import sys input = sys.stdin.readline n = int(input()) dp = [0, 3, 7] + [0] * (n - 2) for i in range(3, n+1): dp[i] = (dp[i-2]+(dp[i-1] * 2)) % 9901 print(dp[n]) 풀이 점..
[Python] 백준 알고리즘 온라인 저지 1149 RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이전의 집과 색이 같지 않고, 다음 집의 색이 같지 않아야 한다. 이 조건을 만족하며 비용의 최솟값 또한 고려해야 한다. 알고리즘 분류 다이내믹 프로그래밍 소스코드 import sys input = sys.stdin.readline n = int(input()) RGB = [list(map(int, input()...
[Python] 백준 알고리즘 온라인 저지 15988 1, 2, 3 더하기 3 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 정수 n을 1, 2, 3의 합으로 표현해야 한다. 표현하는 방법이 어느 정도 규칙적인 것 같아 규칙을 찾아 풀이하기로 했다. 알고리즘 분류 다이내믹 프로그래밍 소스코드 import sys input = sys.stdin.readline dp = [1,2,4,7] for i in range(int(input())): n = int(input()) for j in range..
[Python] 백준 알고리즘 온라인 저지 2225 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 이해는 오래 걸리지 않았다. 예를 들면 인풋이 20 2 일 때 1+19, 2+18... 같은 경우의 수의 개수를 구해야 한다. 알고리즘 분류 다이내믹 프로그래밍 수학 소스코드 import sys input = sys.stdin.readline n, k = map(int, input().split()) dp = [[0] * 201 for _ in range(201)] for i in range(1, 201): dp[1][i] = i for i in range(2..
🚀 새로운 블로그로 이전했습니다.
살펴보러 가기
