IT-garden

문제

위 그림은 크기가 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

문제

널리 잘 알려진 자료구조 중 최대 힙이라는 것이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

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

입력

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

출력

입력에서 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:
            print(-heapq.heappop(h))
        else:
            print(0)
    else:
        heapq.heappush(h, -i)

최소힙과 반대로 -를 넣고 출력합니다.

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

문제

널리 잘 알려진 자료구조 중 최소 힙이라는 것이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

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

입력

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

출력

입력에서 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:
            print(heapq.heappop(h))
        else:
            print(0)
    else:
        heapq.heappush(h, i)

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