DHistory

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 import sys t = int(sys.stdin.readline().rstrip()) def solution(n, a, b): d = [[0, 0] for _ in range(n + 1)] d[1][0] = a[1] d[1][1] = b[1] for i in range(2, n + 1): d[i][0] = max( max(d[i - 2][0], d[i - 2][1]) + a[i], d[i - 1][1] + a[i], ) d[i][1] =..

문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 """ 계단 수: 인접한 모든 자리의 차이가 1이다. 2자리 이상인 경우 마지막으로 끝나는 수: 0, 9 => 1개씩만 존재 나머지는 2개씩 존재 """ n = int(input()) MOD = 1000000000 def solution(n): d = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] for _ in range(n + 1)] d[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in range(2, n + 1): for j in range(10): if j == 0: d[i][j] = d[i - 1][1] % MOD c..

문제 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..