[BOJ] 1476. 날짜 계산

문제 : https://www.acmicpc.net/problem/1476

접근

• 문제자체는 브루트 포스로 풀면되는 아주 쉬운 문제이지만, 다른 사람의 코드를 읽다가 미처 몰랐던 접근법을 발견했다.
• 바로 answer나 cnt 변수를 따로 만들지 않고 나머지 연산(%)를 이용하여 입력 받은 값과 일치할 때까지 for문을 도는 것이다.

코드

if __name__ == "__main__":
    E, S, M = map(int, input().split())
    max_num = 2147000000
    for i in range(1, max_num):
        if (i-E) % 15 == 0 and (i-S) % 28 == 0 and (i-M) % 19 == 0:
            print(i)
            break

풀이

• E, S, M 각각에 대해 나머지 연산의 결과가 모두 0일 때 참이 되는 조건문을 활용할 수 있다.

• 준규가 사는 나라의 방식으로 올해가 다음과 같다고 하자.
  • E = 1
  • S = 1
  • M = 1
• i = 1이라 할 때 (i-E) % 15, (i-S) % 28, (i-M) % 19는 각각 다음과 같다.
  • (1-1) % 15 = 0, (1-1) % 28 = 0, (1-1) % 19 = 0
• 모든 나머지 연산의 결과가 0이므로 우리가 사용하는 연도 방식으로 올해는 i = 1년임을 알 수 있다.

• 또 준규가 사는 나라의 방식으로 올해가 다음과 같다고 하자.
  • E = 13
  • S = 28
  • M = 9
• i = 1부터 반복문으로 나머지 연산을 반복한다고 하면 다음과 같다.
  • i = 1 : -12, -27, -8
  • i = 2 : -11, -26, -7
  • i = 3 : -10, -25, -6
    ...
  • i = 28 : (28-13) % 15 = 0, (28-28) % 28 = 0, (28 - 9) % 19 = 0
• 즉 올해는 i = 28년임을 알 수 있다.
• 때문에 가능한 최대 범위로 for문을 돌게 한 다음, 모든 나머지 연산 값이 0이되는 조건 i를 찾으면 이를 출력하고 break하는 것으로 우리가 사용하는 연도를 출력할 수 있다.

어디에 또 쓸 수 있을까?

• 브루트 포스 알고리즘으로, 특정 step씩 값을 증가해가며 답이 조건에 맞는지 체크해야하는 문제에서 유용한 방법이 될 것 같다.