사용자 도구

사이트 도구


ps:problems:boj:25194

결전의 금요일

ps
링크acmicpc.net/…
출처BOJ
문제 번호25914
문제명결전의 금요일
레벨실버 1
시간복잡도O(n)
인풋사이즈n<=1000
사용한 언어Python
제출기록30840KB / 76ms
최고기록64ms
해결날짜2022/11/15
출처

제1회 곰곰컵

풀이

  • 합이 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) 에 해결된다.

코드

"""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()

토론

댓글을 입력하세요:
K V X T M
 
ps/problems/boj/25194.txt · 마지막으로 수정됨: 2022/11/21 16:18 저자 teferi