문제
생일(일, 월, 연도)이 주어졌을 때 그해 그 날까지 지난 날의 수(연중 날짜 번호)를 출력한다. 윤년이면 2월이 29일이므로 2월 이후 날짜에는 1일을 추가한다. 0 0 0이 입력되면 종료한다.
입력
여러 줄에 걸쳐 day month year 형식으로 입력된다. 0 0 0이 오면 종료한다.
1 1 2000
29 2 2000
1 3 1900
0 0 0출력
각 날짜에 대해 해당 연도의 1월 1일부터 시작하는 날짜 번호를 출력한다.
1
60
60예제
| 입력 | 출력 |
|---|---|
1 1 2000 | 1 |
29 2 2000 | 60 |
1 3 1900 | 60 |
0 0 0 | (종료) |
풀이
1월부터 해당 월의 직전 달까지 각 달의 일수를 누적한 뒤 일(day)을 더한다. 윤년이고 입력 월이 3월 이후이면 1일을 추가한다.
0 0 0이 입력되면 종료한다.- 입력 연도가 윤년인지 판별한다 —
year % 4 == 0이고 (year % 100 != 0이거나year % 400 == 0). - 1월부터
month - 1월까지의 일수 합을 배열mArr로 누적한다. - 윤년이고
month > 2이면totalDay에 1을 추가한다. - 마지막으로
day를 더하여 출력한다.
핵심 아이디어: 각 달의 일수를 미리 배열에 저장하고 prefix sum 방식으로 누적하면 O(12) = O(1)에 계산된다. 윤년 처리는 2월 이후 날짜에만 적용되므로 month 조건으로 분기한다.
코드
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int main(int argc, char *argv[])
{
int day, month, year;
int specialYear;
int totalDay;
int mArr[12] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};
while (1)
{
cin >> day;
cin >> month;
cin >> year;
if (day == 0 && month == 0 && year == 0)
{
break;
}
specialYear = 0;
if (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0))
{
specialYear = 1;
}
totalDay = 0;
if (specialYear == 1 && month > 2)
{
++totalDay;
}
for (int i = 0; i < month; ++i)
{
totalDay += mArr[i];
}
totalDay += day;
cout << totalDay << endl;
}
return 0;
}복잡도
- 시간: O(Q * 12) = O(Q) — Q는 입력 쿼리 수, 각 쿼리마다 최대 12번 반복
- 공간: O(1) — 고정 크기 배열과 변수만 사용