백준 12438 (C++) 새로운 달력 (Large)

최초 업로드: 2025-04-12 03:10:54

최근 수정 시간: 2025-07-25 09:59:58

게시자: rlatjwls3333

카테고리: 백준

# [Gold V] 새로운 달력 (Large)

#### [문제 링크](https://www.acmicpc.net/problem/12438)

## 문제 설명

<p>태양계 밖에서 새로 발견된 행성 ELG8-G는 지구와는 다른 자전/공전주기를 가지고 있어서 지구의 달력을 그대로 가져다 쓸 수 없다. 이에 과학자들은 이 행성을 위해 새로운 달력 시스템을 만들기로 하였다. 그동안 지구에서 사용하던 그레고리력은 매달 날짜가 달라 다소 번거로운 점이 있어 이번 새로운 달력 시스템에서는 매달 같은 일수를 포함하도록 하였다. 이렇게 만들어 놓은 달력을 기반으로 매일 관찰한 내용을 기록하기 위해 커다란 달력을 만들기로 하였는데, 1년을 몇 달로 하는지, 1주를 며칠로 하는지에 따라서 달력이 크기가 달라진다는 사실을 알게 되었다. 이에 과학자들의 편의를 위해 기준이 되는 수들을 입력하면 필요로 하는 달력의 줄 수를 출력해 주는 프로그램을 작성하게 되었다.</p>

<p>한 달에 11일이고, 1년에 3달이며, 한 주에 4일이면 다음과 같은 11줄짜리 달력이 만들어진다.</p>

## 입력

## 출력

<p>각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 달력을 만드는데 필요한 줄 수 이다.</p>

## 풀이
#### 새로운 달력 (Small) 문제와 달리 제한이 커서 시뮬레이션으로 풀 수 없습니다.
#### 먼저 빈 줄이 더 생기는 경우는 각 달이 끝났을 때 달력을 끝까지 채우지 못하는 경우 한 가지입니다.
#### 총월수를 tm로, 월당일수를 md로, 주당일수를 wd로 두고 풀이하겠습니다. 첫 번째 달이 끝날 때에는 (md%wd) 까지 채울 수 있습니다. 이 값이 쌓이다 (md%wd)와 (wd)의 최소 공배수만큼 채워진다면 달력의 끝에 도달하여, 빈 줄이 생기지 않을 것입니다. 이 주기는 wd를 (md%wd)와 (wd)의 최대 공약수로 나눈 값입니다. 총 빈 줄이 생길 수 있는 줄은 tm-1이고, 이 중에서 빈 줄이 생기지 않는 횟수는 (tm-1)/(wd/gcd(md%wd, wd)) 이기에 두 값을 빼면 됩니다.

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for(int tc=1;tc<=t;tc++) {
        long long a, b, c; cin >> a >> b >> c;
        cout << "Case #" << tc << ": " << a-1 - (a-1)/(c/gcd(b%c, c)) + (a*b+c-1)/c << '\n';
    }
}
```