백준(BOJ) 25194 결전의 금요일(Python)

 

 

문제 내용.

 

DP 문제.

처음에는 set으로 다 넣으면서 풀어보려 했는데 시간 초과가 나서 뭐가 잘못된 것 같았다.

처음에는 DP를 생각했지만 일단 그냥 풀어보자는 식이었는데, 결국 DP로 돌아왔다.

DP로 풀려고 하니 리스트 크기를 잡는게 안 돼서 뭐지 했는데, 어짜피 문제에서 요구하는 건 특정한 합을 7로 나눈 나머지가 4가 되는 경우를 찾는 거라 입력받은 모든 A를 7로 나눈 나머지를 가지고 연산을 해도 상관이 없었다.

그렇게 하면 DP 리스트 크기를 6001로 잡을 수 있어 편했다.

그 후에는 그냥 각각 일을 마친 날을 1로 바꾸면서 모든 값을 탐색했다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

n=int(input())
L=list(map(int,input().split()))
for i in range(n):
    L[i]%=7
DP=[0]*6001
DP[0]=1
for i in range(n):
    check=[0]*6001
    for j in range(6001):
        if DP[j] and j+L[i]<=6000 and not DP[j+L[i]] and not check[j]:
            DP[j+L[i]]=1
            check[j+L[i]]=1
for i in range(4,6001,7):
    if DP[i]:
        print('YES')
        sys.exit(0)
print('NO')

나도 운동가야 하는데