[백준 1476] 날짜 계산 (C#, C++) - soo:bak

문제 링크

1476번 - 날짜 계산

설명

서로 다른 세 개의 주기 E S M이 주어졌을 때,

1 1 1 을 기준으로 E S M 이 되는 가장 빠른 해를 구하는 문제입니다.

E, S,M 은 각각 지구, 태양, 달의 주기를 나타내며 다음과 같은 범위를 가집니다:

• 지구 주기: 1 ≤ E ≤ 15
• 태양 주기: 1 ≤ S ≤ 28
• 달 주기: 1 ≤ M ≤ 19
  

각 수는 자신의 범위를 넘어가면 1부터 다시 시작하므로, 지구는 15년마다, 태양은 28년마다, 달은 19년마다 반복됩니다.

예를 들어, E = 1, S = 16, M = 16이면 16년이 가장 빠른 해입니다.

접근법

• 모든 조합을 시도하는 완전탐색 방식으로 해결합니다.
• 가장 빠른 방법은 지구 주기(15년)을 기준으로 반복하는 것입니다.
  세 주기 중, 지구의 주기가 가장 짧기 때문입니다.
• 따라서, E부터 시작하여, 매 반복마다 15를 더해가며
  \(y \equiv S \ (\text{mod } 28),\ y \equiv M \ (\text{mod } 19)\)
  조건을 만족하는지 확인합니다.
• 세 주기의 최소 공배수는 \(15 \times 28 \times 19 = 7980\)이므로
  최악의 경우라도 최대 7980회 이하의 반복으로 해를 구할 수 있습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var tokens = Console.ReadLine().Split();
    int e = int.Parse(tokens[0]);
    int s = int.Parse(tokens[1]);
    int m = int.Parse(tokens[2]);

    int year = e;
    while (year % 28 != s % 28 || year % 19 != m % 19)
      year += 15;

    Console.WriteLine(year);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int e, s, m; cin >> e >> s >> m;

  int y = e;
  while (y % 28 != s % 28 || y % 19 != m % 19)
    y += 15;

  cout << y << "\n";

  return 0;
}