[백준 1507, 9655, 17271, 14495, 1149] - Python

취알스 6주차 최단거리 - 4/4

1507 궁금한 민호

import sys
input = sys.stdin.readline

n = int(input())
graph = [[] for i in range(n)]
edge = [[1 for i in range(n)] for j in range(n)]
# 도로가 있는지 저장(있으면 1, 없으면 0)
result = 0
for i in range(n):
    graph[i] = list(map(int, input().split()))

for k in range(n):
    for a in range(n):
        for b in range(n):
            if k == a or a == b or b == k:
                continue
            if graph[a][b] == graph[a][k]+graph[k][b]: 
            # 1~5 == 1~3 + 3~5 일 경우 1~5 길을 없앰
                edge[a][b] = 0
            elif graph[a][b] > graph[a][k]+graph[k][b]: 
            # 주어진 그래프 graph는 이미 최단거리 알고리즘이 
            # 적용되었기 때문에 더 짧은 길이 있을 수가 없음.
            # 모순이 되는 경우를 찾는 것임!
                result = -1

if result != -1:
    for i in range(n):
        for j in range(i, n):
            if edge[i][j]:
                result += graph[i][j]
print(result)

취알스 7주차 DP - 4/4

9655 돌 게임

n = int(input())
if n % 2:
    print("SK")
else:
    print("CY")

가져갈 수 있는 돌의 갯수가 1, 3밖에 없다. sk는 홀수번째 턴에 돌을 가져가기 때문에 n이 홀수라면 무조건 sk가 이긴다. 반대로 n이 짝수일때는 cy가 가져가는 돌이 무조건 짝수번째이기 때문에 cy가 우승.

17271 리그 오브 레전설(Small)

n, m = map(int, input().split())
ans = 0
dp = [1]*(n+1)
if n>=m:
    dp[m] = 2
# m초 전까지는 스킬 A만 쓸 수 있기 때문에 경우의 수가 1밖에 없음.
for i in range(m+1, n+1):
    dp[i] = (dp[i-1]+dp[i-m])%1000000007
    # i초에 가능한 조합은 1초 전에 스킬 A 쓰기 + m초 전에 스킬 B 쓰기
print(dp[n]%1000000007)

14495 피보나치 비스무리한 수열

n = int(input())
fibo = [0] * 117
fibo[1] = 1
fibo[2] = 1
fibo[3] = 1
for i in range(4, n+1):
    fibo[i] = fibo[i-1] + fibo[i-3]
print(fibo[n])

1149 RGB 거리

import sys
input = sys.stdin.readline

n = int(input())
graph = []
dp=[]
for i in range(n):
    graph.append(list(map(int, input().split())))
    dp.append([0,0,0])
dp[0] = graph[0]

for i in range(1, n):
    # R
    dp[i][0] = min(graph[i][0] + dp[i-1][1], graph[i][0] + dp[i-1][2])
    # G
    dp[i][1] = min(graph[i][1] + dp[i-1][0], graph[i][1] + dp[i-1][2])
    # B
    dp[i][2] = min(graph[i][2] + dp[i-1][0], graph[i][2] + dp[i-1][1])

print(min(dp[n-1]))