목록Computer Science (228)
DHistory
문제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 """ RGB 거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 모든 집을 칠하는 비용의 최솟값은? 1. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. 2. N번 집의 색은 N-1번 집의 색과 같지 않아야한다. 3. i번째 집의 색은 i-1번 / i+1번 집의 색과 같지 않아야 한다. """ import sys n = int..
문제 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split())) def soluion(a): d = [1] * len(a) for i in range(1, len(a)): for j in range(1, i): if a[i] < a[j] and d[i] < d[j] + 1: d[i] = d[j]..
문제 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 풀이 """ Ai 이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 최소 몇 번 점프를 해야 갈 수 있는지 구하시오. 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력 d[n]: n칸에 도달했을 때, 최소 점프 횟수. 10 1 2 0 1 3 2 1 5 4 2 10 1 0 0 0 0 0 0 0 1 0 """ import sys n = int(sys.stdin.readlin..
문제 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 """ 1 = 1 2 = 2 3 = 1 + 2 2 + 1 3 4 = 1 + 2 + 1 (3을 만들 수 있는 경우 중 2개) 1 + 3 3 + 1 (1을 만들 수 있는 경우 중 1개) 5 = 1 + 3 + 1 2 + 1 + 2 3 + 2 2 + 3 6 = 2 + 1 + 2 + 1 2 + 3 + 1 3 + 2 + 1 1 + 2 + 1 + 2 1 + 3 + 2 3 + 1 + 2 1 + 2 + 3 2 + 1 + 3 """ import sys MOD = 1000000009 t = int(sys.stdin.read..
문제 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 import sys MOD = 1000000009 t = int(sys.stdin.readline().rstrip()) d = [0] * 1000001 result = [] def solution(n): if n
문제 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split())) def solution(a): d = [1] * len(a) for i in range(1, n + 1): for j in range(1, i): if a[i] < a..
문제 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 n = int(input()) def solution(n): d = list(range(n + 1)) for i in range(1, n + 1): for j in range(int(i ** .5), 0, -1): if i == j * j: d[i] = 1 elif i > j * j: d[i] = min(d[i - j * j] + d[j * j], d[i]) return d[n] print(solution(n))..
문제 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 """ 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 5 1 1 6 15 15 6 1 1 7 21 30 21 7 1 """ n, k = map(int, input().split()) MOD = 10007 def solution(n, k): k = min(n - k, k) d = [[0] * (n + 1) for _ in range(n + 1)] d[0][0] = d[1][0] = d[1][1] = 1 for i in range(2, n + 1): for j in range(n + 1): d[i][j] =..
문제 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 풀이 """ 가장 큰 증가하는 부분 수열의 합 """ import sys from copy import deepcopy n = int(sys.stdin.readline().rstrip()) numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split()))[:n] def solution(a): d = deepcopy(a) for i in ra..
문제 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 """ d[n]: 연속된 몇 개의 수를 선택하여 가장 큰 합 """ import sys n = int(sys.stdin.readline().rstrip()) numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split()))[:n] def solution(a): d = [0] * len(a) for i in range(1, len(a)): d[i] = max(d[i - 1] + a[i], a[i]) ret..