[AtCoder - ARC032A] ホリドッグ

난이도: 178

 

번역

Holidog는 굉장히 똑똑한 개입니다. 얼마나 똑똑하냐면, 덧셈과 소수 판별을 할 수 있습니다! Holidog에게 어떠한 양의 정수를 주고 이 수가 소수인지 묻는다면, 소수라면 WANWAN이라고 짖고, 아니라면 BOWWOW라고 짖습니다.

 

당신은, 이 Holidog에게 \( 1 + 2 + 3 + \ldots + N \)이 소수인지 묻기로 했습니다. 이 때 Holidog가 어떻게 짖을 지 출력하세요.

 

소수란, \( 2 \) 이상의 양의 정수 중 \( 1 \)과 자기 자신을 제외한 다른 양의 정수로 나누어지지 않는 수를 의미합니다. 예로, \( 2 \), \( 3 \), \( 17 \)은 소수이지만, \( 1 \), \( 10 \)은 소수입니다.

태그

• Mathematics
  • Number Theory
    • Primality Test

1. 간단한 풀이

\( N \le 1\,000 \)이기 때문에, 그냥 \( 1 + 2 + 3 + \ldots + N \)을 반복문으로 계산한 뒤 이게 소수인지 반복문으로 계산하는 풀이도 충분히 통과합니다.

2. 하지만 재밌는 짓을 해본다면?

[1]만 알아도 이 문제를 푸는 데에는 지장이 없습니다. 하지만 조금 재밌는 일을 해봅시다.

 

\( 1 + 2 + \ldots + N = \frac{N(N+1)}{2} \)입니다. 이 식을 조금 생각해본다면, \( N \ge 3 \)이라면 분자에 \( 4 \) 이상의 짝수가 항상 들어가게 되므로, 항상 합성수가 됩니다.

남은 경우는 \( N = 1 \)과 \( N = 2 \)로, 각각 합이 \( 1 \)과 \( 3 \)이기 때문에 각각 합성수, 소수가 됩니다.

 

따라서, \( N = 2 \)를 제외하고는 모두 합성수이므로 BOWWOW를, \( N = 2 \)에는 WANWAN을 출력하면 됩니다.

코드

예전 AtCoder 문제는 줄 끝에 NewLine Character가 없으면 WA 처리를 받으니 주의하세요.

 

void Main(){
    int n; cin >> n;
    if (n == 2){ cout << "WANWAN" << endl; }
    else{ cout << "BOWWOW" << endl; }
}