[Kotlin, B1] 백준 31432번 소수가 아닌 수 3

출처: unsplash.com

소수가 아닌 수 3(31432번)

Bronze 1

#수학 #애드 혹 #정수론

 

문제 내용

 

 

문제 접근

n개의 숫자를 사용해서 소수가 아닌 수가 있으면 yes를 출력하고 소수가 아닌 수 하나를 아무거나 출력하고, 소수가 아닌 수가 없을 때는 no를 출력하는 문제이다.

각 숫자는 중복해서 사용할 수 있다.

 

약간의 수학적 고민이 필요한 문제이다.

 

같은 숫자를 중복해서 쓸 수 있다는 경우 때문에 no가 나오는 경우는 하나도 없다.

n개의 숫자가 2, 3, 5, 7인 경우에는 n의 숫자들이 모두 소수이지만, 같은 숫자를 여러 번 쓸 수 있으면 22, 33, 55, 77처럼 소수가 아닌 수를 언제든지 만들 수 있다는 뜻이 되기 때문에 n에 어떤 수가 나와도 no가 나오는 경우가 없어지는 것이다.

 

그러면 정답을 같은 수를 사용할 수 있게 해주는 연속된 1을 곱해서 출력하면 된다.참고로 0과 1 모두 소수가 아니다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val d = readLine().split(" ").map { it.toInt() }

    println("YES")
    println(d.last() * 111)
}

 

문제 풀이

입력값에서 가장 마지막 값이 111을 곱해서 문제를 해결하였다.

 

문제 해결 과정

기존에는 11을 곱한 결과를 제출하였지만 오답이 나왔다.

생각해 보니까 d에 1밖에 없고, 1에 11을 곱하면

yes와 11이 나오게 되는데 11은 소수이다. 이 case에서 오답이 나오게 된다.

그래서 111을 곱한 수를 출력해 문제를 해결해 주었다.

0 ~ 9에 111을 곱한 수(0, 111, 222, 333...)들은 모두 소수가 아니다.