[AtCoder - ARC032A] ホリドッグ

난이도: 178

 

번역

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

 

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

 

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

태그

• Mathematics
  • Number Theory
    • Primality Test

1. 간단한 풀이

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

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

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

 

$1+2+\dots +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; }
}