테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 결전의 금요일 ======

===== 풀이 =====
  * 합이 7k+4 형태가 되는 부분집합이 존재하는지를 찾으면 된다.
  * 7의 배수인 숫자는 포함하든 안하든 7로 나눈 나머지에 영향을 주지 않으니까 제외시키고, 나머지 7k+c인 숫자들은 포함시키게 되면, 7로 나눈 나머지가 바뀌게 된다. 결국 7의 배수가 아닌 숫자가 6개 이상 있으면 합이 7k+l 이 되는 부분집합을 모든 l에 대해서 다 만들수 있다. 
  * 그래서 7의 배수가 아닌숫자가 6개 이상이면 무조건 YES, 5개 이하면 모든 조합을 다 만들어서 7k+4가 있는지 확인해보면 된다.
  * 실제 구현은 7의 배수인지 아닌지를 체크하고 하는것도 귀찮아서, 그냥 무조건 모든 조합을 다 만들어 보게 구현했다. 그래도 값의 종류가 7개밖에 없으므로, 시간복잡도는 O(7*N)=O(N) 에 해결된다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 25194. 결전의 금요일".

- Problem link: https://www.acmicpc.net/problem/25194
- Solution link: http://www.teferi.net/ps/problems/boj/25194
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    days = {0}
    for a_i in A:
        days.update({(x + a_i) % 7 for x in days})
    print('YES' if 4 in days else 'NO')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_1}}