[백준 BOJ / Python] 25194번 결전의 금요일 DP

문제

각각의 일을 끝내는 데 걸리는 시간(일)이 담겨 있는 A 배열이 주어졌을 때, 일의 순서를 바꾸어 헬스장에 갈 수 있는 경우는 YES, 갈 수 없다면 NO를 출력하는 문제이다.

 

문제 조건

1. 오늘은 월요일이다.
2. 금요일에 일을 끝내야 헬스장에 간다.

풀이

• 일주일은 7일이기 때문에 월요일부터 일요일을 0에서 6으로 둔다.
• 월요일에 일을 시작해서 금요일에 끝나려면 7로 나누었을 때 나머지가 4인 날이 있는지 확인하면 된다.
• 따라서 숫자의 조합에 따라 합계를 7로 나눈 나머지가 4가 되는 경우가 있는지 살핀다.
• 시간에 대한 연산과 나머지에 대한 연산의 결과가 같다는 것을 활용한다. 
  ex) (15+ 9) % 7 = (1 + 2) % 7 = 3
• A 배열의 요소(a)들을 모두 순회하면서 먼저 계산된 나머지와 연산을 하면 모든 조합을 다 계산할 수 있다.
• 즉 선행 요소의 결과는 변하지 않고, 이후 요소들과의 정해진 공식을 사용하면됨으로 dp 사용이 가능하다.
• 나머지의 존재 여부를 표시한 리스트를 순회하면서 나머지가 존재한다면 나머지 계산을 이어나가기 때문에, 나머지 0을 두어 자기 자신 값(a)과 더할 수 있도록 한다.

• 예시) A로 5,3,2 이 주어진다면, 아래 그림과 같이 연산된다. (j는 나머지 숫자가 존재함을 의미)

알고리즘

1. 나머지 정보를 담을 리스트를 생성한 뒤, 나머지 0을 1로 초기화한다.
2. for문 루프를 통해 A 배열에서 하나씩 꺼내어 나머지 연산을 한다.
3. 임의로 계산값을 담아둘 리스트(temp)를 생성한다.
   • temp 리스트를 생성하는 이유는 dp 리스트를 하나로 사용한다면 새로운 나머지를 추가하는 과정에서 dp 리스트에 담기지 않았던 나머지가 표시되어 한번 더 계산될 수 있기 때문이다.
4. 나머지들이 담긴 dp 리스트를 순회하면서 0~6 중 나머지가 존재한다면, 현재 시간 a를 더해 나머지 연산을 하고 새로운 나머지를 표시한다.
5. 기존 dp 리스트에 있던 나머지도 temp 리스트에 표시해 준다.
6. dp 리스트를 temp 리스트로 업데이트 한다.
7. A 리스트의 모든 요소를 순회하고 난 뒤 나머지 4가 있다면 YES를 없다면 NO를 출력한다.

Python 코드

import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))
dp = [0]*7 # 나머지를 담을 dp
dp[0] = 1 # 나머지 0

for a in A: # A의 요소 하나씩 꺼냄
    temp = [0]*7
    for j in range(7): 
        if dp[j]:               # 만약 나머지 j가 이미 있다면
            temp[(a+j) % 7] = 1 # 거기에 a를 더하고 나머지 연산을 한다.
            temp[j] = 1        
    dp = temp # 이전에 계산된 내용들과 지금 숫자와 계산해서 새롭게 생긴 나머지가 섞이지 않기 위해 분리
if dp[4]:
    print("YES")
else: 
    print("NO")

문제 출처

25194번: 결전의 금요일