[dp/완탐] 백준 25194 파이썬 (결전의 금요일) 실버1 곰곰컵

-풀이

import sys
input = sys.stdin.readline
work_count = int(input())
work_arr = list(map(int,input().split()))

#월~일
dp = [False for _ in range(7)]
#월요일 시작이라서 True
dp[0] = True

for i in range(work_count):
  days = []
  for j in range(7):
    if dp[j] == True:
      days.append((j+work_arr[i])%7)
  for k in days:
    dp[k] = True
print("YES" if dp[4]==True else "NO")

-풀이설명

백준 곰곰컵 D 문제로, 대회 당일 맞았었는데, 재채점이 되어 오답처리가 되었다. 틀리고나서 내 코드를 보고 다시 고민을 해보니 생각보다 틀린 부분이 꽤 있었다. 조합을 이용하여 풀려고했지만 시간초과가 뜨고 잘 되지 않아서 결국 dp로 푸는 방법을 선택했는데, 잘 풀리지 않아 취준 단톡방을 이용하여 도움을 받아 해결하였다. 

dp는 풀이를 보면 간단해보이는데 직접 생각해서 구현하기가 잘 되지 않는다.

월~일요일을 표시해주는 dp를 만들어 일을 하고 난 후의 요일을 dp인덱스에 넣어서 True로 만들어주어 그 다음 일을 하고 난 후의 요일을 누적해주어 % 7 을 해주면서 나갈 수 있는 요일을 찾아 True로 바꿔준다 그러고 난 후 마지막에 dp[4]  == True 즉, 금요일에 나갈 수 있게 되어있다면, YES를 출력해준다.