IT-garden

문제

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.

4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 회원의 수만큼 붙어 있다. 마지막 줄에는 -1이 두 개 들어있다.

출력

첫째 줄에는 회장 후보의 점수와 후보의 수를 출력하고, 두 번째 줄에는 회장 후보를 오름차순으로 모두 출력한다.

예제 입력과 출력

알고리즘 분류

플로이드 와샬 알고리즘 

정답

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

INF=sys.maxsize

n=int(input())
a=[[INF]*(n+1) for i in range(n+1)]

while True:
    s1,s2=map(int,input().split())
    
    if s1 == -1 and s2 == -1:
        break
    a[s1][s2] = 1
    a[s2][s1] = 1

for i in range(1,n+1): # 자기자신의 경로
    a[i][i] = 0

for k in range(1,n+1): # 거치는 거
    for i in range(1,n+1):
        for j in range(1,n+1):
            if a[i][j] == 1 or a[i][j] == 0:
                continue
            elif a[i][j] > a[i][k] + a[k][j]:
                a[i][j] = a[i][k] + a[k][j]     

r=[]
for i in range(1,n+1):
    r.append(max(a[i][1:]))

m=min(r)
print(m, r.count(m))
for i,v in enumerate(r):
    if v == m:
        print(i+1,end=' ')

전체 배열을 INF로 하고 자기자신으로 가는 경로는 0으로 설정합니다.
플로이드 와샬 알고리즘을 적용하고 각 행에서 가장 큰 값을 각 회원의 점수로 매깁니다.
점수들 중 가장 작은 값을 회장 후보의 점수로 삼고 후보의 수와 회장 후보를 출력합니다.

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

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

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

n=int(input())
a=[0]*(n+1)

for i in range(1,n+1):
    a[i]=int(input())

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

if n == 2:
    dp[2]=dp[1]+a[2]
elif n > 2:
    dp[2]=dp[1]+a[2]
    for i in range(3,n+1):
        dp[i]=max(dp[i-3]+a[i-1], dp[i-2]) + a[i]
        dp[i]=max(dp[i-1], dp[i])

print(dp[n])

dp[i-3] + a[i-1] + a[i] : 전 와인 먹고 다음에 와인 먹기
dp[i-2] + a[i] : 전전 와인 먹고 한 칸 뛰고 다음 와인 먹기

max(dp[i-1], dp[i]): 현재의 와인 먹을지 말지 결정(와인을 무조건 마셔야 하는 것은 아니기 때문에!)

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

문제

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