IT-garden

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())

dp=[[0]*10 for i in range(n+1)]

for i in range(1,10):
    dp[1][i]=1

if n == 1:
    print(sum(dp[1]))
else:
    for i in range(2,n+1):
        for j in range(10):
            if j == 0:
                dp[i][j] = dp[i-1][j+1] 
            elif j == 9:
                dp[i][j] = dp[i-1][j-1] 
            else:
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) 
    print(sum(dp[n]) % 1000000000)

N = 1 : 1 2 3 4 5 6 7 8 9

N = 2 : 10 12 23 34 45 56 67 78 89 21 32 43 54 65 76 87 98

N = 3 : 123 234 345 456 567 678 789 210 321 432 543 654 765 876 987 101 121 212 232 323 434 343 454 545 565 656 676 767 787 878 898 989

N = 1 : 9개
N = 2 : 17개
N= 3 : 32개

N일때의 숫자 개수로는 점화식을 찾지 못하고 뒷자리 수로 점화식을 세웠습니다.

dp[N의 수][N자리 숫자일 때 일의 자리의 수]

일의 자리의 수는 0부터 9까지 가능합니다.

일의 자리수가 0과 9일때와 2~8인 경우를 나눠서 생각합니다.

일의 자리수 = 0 : dp[n][j] = dp[n-1][j+1]
일의 자리수 = 9 : dp[n][j] = dp[n-1][j-1]
일의 자리수가 2부터 8인 경우 : dp[n][j] = (dp[n-1][j-1] + dp[n-1][j+1])

백준 알고리즘 10844번 : https://www.acmicpc.net/problem/10844

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[]
a.append(0)

for i in range(1,n+1):
    a.append(int(input()))

dp=[0] *(n+1)
dp[1]= a[1]

if n == 1:
    print(dp[n])
    exit(0)
elif n == 2:
    dp[2]= max(a[1] + a[2], a[2])
elif n == 3:
    dp[2]= max(a[1] + a[2], a[2])
    dp[3]= max(a[1] + a[3], a[2] + a[3])
else:
    dp[2]= max(a[1] + a[2], a[2])
    dp[3]= max(a[1] + a[3], a[2] + a[3])
    for i in range(4,n+1):
        dp[i] = max(dp[i-3] + a[i-1] + a[i], dp[i-2] + a[i])

print(dp[n])

dp[1]이 첫번째 계단을 오르는 경우만 있습니다.
dp[2]는 첫번째에서 한 계단 오르는 것이나 처음부터 두 계단 오르는 것 중 큰 경우를 선택합니다.
dp[3]는 첫번째에서 두 계단 오르는 것, 두번째에서 한 계단 오르는 것 중 큰 경우를 선택합니다.

n이 4 이상이면 dp[i]에 값을 구하는 방법은 dp[i-3]에서 두 계단 올라 전 계단을 밟고 한 계단 올라 마지막 계단을 밟는 것, dp[i-2]에서 두 계단 올라 마지막 계단을 밟는 것이 있습니다.

백준 알고리즘 2579번 : www.acmicpc.net/problem/2579

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[]

for i in range(n):
    a.append(list(map(int,input().split())))

for i in range(1,n):
    for j in range(i+1):
        if j == 0:
            a[i][0] = a[i-1][0] + a[i][0]
        elif i == j:
            a[i][j] = a[i-1][j-1] + a[i][j]
        else:
            a[i][j] = max(a[i-1][j-1] + a[i][j], a[i-1][j] + a[i][j])

print(max(a[n-1]))

각각의 경우에 나눠 생각합니다.

 빨간색 : if j == 0:
                a[i][0] = a[i-1][0] + a[i][0]

 파란색 : elif i == j:
                a[i][j] = a[i-1][j-1] + a[i][j]

 초록색 : else:
                a[i][j] = max(a[i-1][j-1] + a[i][j], a[i-1][j] + a[i][j])

백준 알고리즘 1932번 : https://www.acmicpc.net/problem/1932

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다

음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

import sys
input = lambda : sys.stdin.readline().strip()

t=int(input())
a=[int(input()) for i in range(t)]
m=[0]*101
m[1]=1
m[2]=1
m[3]=1

for i in a:
    if i < 4:
        print(m[i])
    elif i >= 4:
        if m[i] != 0:
            print(m[i])
            continue
        
        for j in range(4,i+1):
            m[j] = m[j-2] + m[j-3]
        print(m[i])

문제에서 P(1)부터 P(10)까지의 첫 10개 숫자를 통해 분석해보면
P(1) = 1
P(2) = 1
P(3) = 1
n이 4 이상인 경우 : P(n) = P(n-2) + P(n-3) 라는 규칙이 있습니다.

백준 알고리즘 9461번 : https://www.acmicpc.net/problem/9461

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다.(N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍
수학

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
m=[0]*1000001
m[1]=1
m[2]=2

for i in range(3,n+1):
    m[i]=(m[i-2] + m[i-1]) % 15746

print(m[n])

사용할 수 있는 타일 종류 : '1'과 '00'입니다.

N = 1 이면 1
N = 2 이면 11 00
N = 3 이면 111 100 001
N = 4 이면 1111 1100 1001 0011 0000
N = 5 이면 11111 00111 10011 11001 11100 10000 00001 00100
N = 6 이면 111111 001111 100111 110011 111001 111100 110000 100100 001001 001100 000011 100001 000000

N = 1 이면 1개, N = 2 이면 2개, N = 3 이면 3개, N = 4 이면 5개, N = 5 이면 8개, N = 6 이면 13개

즉, 피보나치 수열의 규칙을 따릅니다.

F(0) = 0, F(1) = 1, F(N) = F(N-1) + F(N-2)

백준 알고리즘 1904번 :www.acmicpc.net/problem/1904 

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력과 출력

알고리즘 분류

힙

정답

import heapq
import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[int(input()) for i in range(n)]

h=[]

for i in a:
    if i == 0:
        if h:
            ab, c= heapq.heappop(h)
            print(c)
        else:
            print(0)
    else:
        heapq.heappush(h, (abs(i),i))

heapq에 값을 (abs(i), i)로 저장합니다.

abs(i)를 통해 절대값이 작은 것부터 heapq에 넣어서 절대값이 작은 것이 앞에 올 수 있게 합니다.

i는 그대로 넣어서 절대값이 같더라도 i가 작은 것이 앞에 올 수 있게 합니다.

백준 알고리즘 11286번 : www.acmicpc.net/problem/11286