FeelingXD

[๋ฐฑ์ค€ -9657] ๋Œ ๊ฒŒ์ž„ 3 ๋ณธ๋ฌธ

์นดํ…Œ๊ณ ๋ฆฌ ์—†์Œ

[๋ฐฑ์ค€ -9657] ๋Œ ๊ฒŒ์ž„ 3

FeelingXD 2024. 1. 5. 02:04

โ“ Problem

๐Ÿค” How

  • DP , ๊ฒŒ์ž„์ด๋ก  ๋ฌธ์ œ ์ด๋‹ค.
  1. DP ํ…Œ์ด๋ธ”์—๋Š” n๋ฒˆ๊นŒ์ง€์˜ ๋Œ๊ฒŒ์ž„์ผ๋•Œ ์Šน๋ฆฌํ•˜๋Š” ๊ฒฝ์šฐ๋ฅผ ํ…Œ์ด๋ธ”์— ์ €์žฅํ•œ๋‹ค. (1์ผ๊ฒฝ์šฐ SK์Šน๋ฆฌ 0 ์ผ๊ฒฝ์šฐ CY ์Šน๋ฆฌ)
  2. ๊ฒŒ์ž„์กฐ๊ฑด์ค‘ "์™„๋ฒฝํ•˜๊ฒŒ" ์ฆ‰ ์ตœ์ ์˜ ๋ฐฉ๋ฒ•์œผ๋กœ ๊ฒŒ์ž„์„ ์ง„ํ–‰ํ•œ๋‹ค.
  • ๊ทธ๋Ÿผ ๋Œ์„ 1,3,4 ๊ฐœ ๋ฅผ ๊ฐ€์ ธ๊ฐ€๋Š” ๊ฒฝ์šฐ์ดํ›„๋Š” ๋‹ค์Œ์€ CY(์ฐฝ์˜)๋งŒ ๋‹ค์Œ๋Œ ์„ ๊ฐ€์ ธ ๊ฐˆ ์ˆ˜์žˆ๋‹ค.
  • ์ด๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ dpํ…Œ์ด๋ธ”์˜ 1,3,4 ๊ฐœ๋ฅผ ์ด์ „์—์„œ ๊ฐ€์ ธ์˜ค๋Š”๊ฒฝ์šฐ๋ฅผ ์ œ์™ธํ•˜๋ฉด ๋‹ค์Œ๊ฒฝ์šฐ๋Š” ๋ฐ˜๋“œ์‹œ ๊ฐ€์ ธ์˜ฌ ์ˆ˜ ์—†๋‹ค.

โ— Solve

#๋Œ ๊ฒŒ์ž„ 3
import sys
input =sys.stdin.readline

def solution():
    n=int(input())
    dp=[1,1,0,1,1]
    for i in range(5,n+1):
        if (dp[i-4]+dp[i-3]+dp[i-1])==3:
            dp.append(0)
        else:
            dp.append(1)
    print("SK" if dp[n] else "CY")
    pass
if __name__=="__main__": # ์‹คํ–‰๋˜๋Š” ๋ถ€๋ถ„
    solution()
    pass