99클럽 코테 스터디 26일차 TIL - DP(백준-전력망을 둘로 나누기)

https://www.acmicpc.net/problem/9655

• 오늘의 학습 키워드 : DP 
• 공부한 내용
  • DP
  • 처음 문제를 보자마자 생각한건.. 이건 무슨 알고리즘인가? 이러고서는 그냥 규칙부터 찾았다.
    N이 짝수인지 홀수인지에 따라 출력이 달라진다고 생각했다.
    짝수인 경우에는 창영이가 이겨서 "CY"
    홀수인 경우에는 상근이가 이겨서 "SK
  • 이 문제에서 상근이와 창영이는 한 번의 차례에 돌을 1개 또는 3개씩 가져갈 수있는데... 1과 3은 모두 홀수이기 때문에:
    
    • 처음 돌의 개수가 홀수이면, 홀수 차례에 상근이가 마지막 돌을 가져감.
    • 처음 돌의 개수가 짝수이면, 짝수 차례에 창영이가 마지막 돌을 가져감.

1️⃣ 처음 풀이

import sys

N = int(sys.stdin.readline().strip())

#짝수 like 2면 끝나는 사람이 이김
#홀수 like 3면 시작하는 사람이 이김
if N%2==0:
    print("CY")
else:
    print("SK")

 

2️⃣ DP로 푼경우

import sys

# 입력값 N을 받음 (돌의 개수)
N = int(sys.stdin.readline().strip())

def stone_game(N):
    # dp[i]: 돌이 i개일 때, 상근이가 이기면 True, 창영이가 이기면 False
    dp = [False] * (N + 1)
    
    # 초기값 설정
    # 돌이 1개일 때: 상근이가 가져가므로 SK 승리
    dp[1] = True

    # 돌이 2개일 때: 상근이가 1개 가져가면 창영이가 마지막 돌을 가져감 → CY 승리
    if N >= 2:  # N이 2 이상일 때만 설정
        dp[2] = False

    # 돌이 3개일 때: 상근이가 3개를 모두 가져가므로 SK 승리
    if N >= 3:  # N이 3 이상일 때만 설정
        dp[3] = True

    # 돌이 4개일 때: 상근이가 1개를 가져가면 창영이가 나머지 3개를 가져감 → CY 승리
    if N >= 4:  # N이 4 이상일 때만 설정
        dp[4] = False

    # 동적 계획법(DP) 계산
    for i in range(5, N + 1):  # 돌이 5개 이상일 때부터 점화식으로 결과 계산
        # dp[i]는 창영이의 패배 상태가 있으면 True
        # 즉, 상근이가 1개를 가져갔을 때(dp[i-1]) 또는 3개를 가져갔을 때(dp[i-3]) 창영이가 지는 경우
        dp[i] = not dp[i - 1] or not dp[i - 3]

    # N개의 돌로 시작했을 때 승자가 상근이면 "SK", 창영이면 "CY" 반환
    return "SK" if dp[N] else "CY"

# 결과 출력
print(stone_game(N))

 

• 오늘의 공부 회고
  • 오랜만에 DP도 풀고 좋은.. 경험..?
  • 이제 새롭게 dp 접근하니깐 오늘의 문제 난이도는 soso 였다고 한다~
  • 마지막으로 서현진 짤로