백준 27065번
https://www.acmicpc.net/problem/27065
문제
생각하기
-
T를 통해 들어오는 여러개의 테스트 케이스에 대한 정답을 도출한다.- 이 경우 memoization을 활용하면 시간 단축을 할 수 있다
- 예를 들어 2022가 과잉수라는 사실은 어떤 다른 테스트 케이스에서도 변함이 없기 때문에 2022에서 사용된 다른 약수들의 결과값들을 다른 테스트 케이스에서도 적용할 수 있기 때문이다.
-
약수를 구하는 알고리즘을 사용해야 한다.
동작
private fun divisor(targetNum: Int): ArrayList<Int> { // 약수를 구하는 메소드
val arr = ArrayList<Int>()
val sqrt = Math.sqrt(targetNum.toDouble()).toInt()
for (i in 1..sqrt) {
if (targetNum % i == 0) {
if (i * i == targetNum) {
arr.add(i)
} else {
arr.add(i)
arr.add(targetNum / i)
}
}
}
return arr
} // End of divisor
가장 첫번째로 해야하는 일이 temp로 들어오는 값의 약수를 구하는 알고리즘이다.
위는 약수를 모두 구하는 메소드이다.
약수의 개수가 몇 개가 될지 모르기때문에 ArrayList에 약수의 값들을 저장한다.
2022의 경우, [1, 2022, 2, 1011, 3, 674, 6, 337] 의 약수가 구해진다.
// 1. N이 과잉수인지 판별.
if (memo[temp] != 0 && memo[temp] != 1) {
// memo[temp]의 값이 0이 아니면서, 1이 아닌 경우에는 과잉수가 아닌게 확실함
sb.append("BOJ 2022").append('\n')
continue
} else if (memo[temp] == 0 && !isAbundantNumber(temp, arr)) {
// memo[temp]가 0이면, 판별 해야되고, 판별한 값이 false일 경우,
sb.append("BOJ 2022").append('\n')
continue
}
이제 위에서 구해진 약수들로
첫 번째 해야할 일이 N이 과잉수인지 판별하면 된다.
N이 과잉수가 아닐 경우 어차피 "Good Bye"를 출력할 수 없기 때문에 더 이상 진행할 필요가 없다.
만약 N이 과잉수 일 경우 다음단계를 진행한다.
이제 N을 제외한 N의 모든 약수들이 과잉수인지 부족수인지를 구해야 한다.
여기서 우리가 memoization을 활용할 수 있는데,
N에서 구해진 약수 [1, 2022, 2, 1011, 3, 674, 6, 337]들의 각 원소들이 과잉수인지, 부족수인지, 완전수인지를 판별해서 memoization으로 저장해두면 다음 테스트케이스에서 겹치는 원소가 있다면 판별하는 과정을 생략하고 곧바로 결과를 도출 할 수 있다
private fun isAbundantNumber(targetNum: Int, arr: ArrayList<Int>): Boolean {
// 해당 값의 약수 배열을 새로 가져와야됨.
val size = arr.size
var sum = 0
for (i in 0 until size) {
if (arr[i] == targetNum) continue
sum += arr[i]
}
if (sum > targetNum) {
// 과잉수이면 true를 return
memo[targetNum] = 1
return true
}
if (sum == targetNum) {
memo[targetNum] = 3 // 완전수
} else {
memo[targetNum] = 2 // 부족수
}
return false
} // End of isAbundantNumber
이제 우리가 가져온 값 targetNum과 targetNum의 약수들을 합해서 targetNum으로 들어온 값이
과잉수인 약수인지를 완전수인지를 판별한다.
그리고 판별된 결과값을 memo배열에 저장한다.
여기서 하나라도 약수중에 과잉수가 있다면 곧바로 false를 return해서 "BOJ 2022"를 출력하도록 한다.
만약 모든 조건을 통과해서 true를 반환했을 경우에는 문제에서 제시한 모든 조건을 통과했으므로
"Good Bye"를 출력한다.
코드
Kotlin
import java.util.*
import java.io.*
import java.lang.StringBuilder
private val memo = IntArray(5_001)
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.`out`))
val sb = StringBuilder()
memo[1] = 2
memo[2] = 2
memo[3] = 3
val T = br.readLine().toInt()
for (i in 0 until T) {
var temp = br.readLine().toInt()
var arr = divisor(temp)
// 1. N이 과잉수인지 판별.
if (memo[temp] != 0 && memo[temp] != 1) {
// memo[temp]의 값이 0이 아니면서, 1이 아닌 경우에는 과잉수가 아닌게 확실함
sb.append("BOJ 2022").append('\n')
continue
} else if (memo[temp] == 0 && !isAbundantNumber(temp, arr)) {
// memo[temp]가 0이면, 판별 해야되고, 판별한 값이 false일 경우,
sb.append("BOJ 2022").append('\n')
continue
}
// 해당 조건을 통과했을 경우, 일단 N은 과잉수가 맞음
// 2. N을 제외한 N의 모든 약수가 부족수이거나 완전수인지를 체크
val size = arr.size
var flag = true
for (j in 0 until size) {
if (arr[j] == temp) continue // 자신은 통과
// 다시 arr[i]의 값이 과잉수 인지 아닌지를 체크함
// 하나라도 arr[i]의 값이 과잉수가 된다면 Good Bye를 출력할 수 없다.
if (memo[arr[j]] == 1) {
sb.append("BOJ 2022").append('\n')
flag = false
break
}
if (memo[arr[j]] == 2 || memo[arr[j]] == 3) {
continue
}
// 과잉수일 경우 BOJ 출력
if (isAbundantNumber(arr[j], divisor(arr[j]))) {
sb.append("BOJ 2022").append('\n')
flag = false
break
}
}
// 모든 조건을 통과 했을 때,
if (flag) {
sb.append("Good Bye").append('\n')
}
} // End of for(T)
bw.write(sb.toString())
bw.close()
} // End of main
private fun divisor(targetNum: Int): ArrayList<Int> {
val arr = ArrayList<Int>()
val sqrt = Math.sqrt(targetNum.toDouble()).toInt()
for (i in 1..sqrt) {
if (targetNum % i == 0) {
if (i * i == targetNum) {
arr.add(i)
} else {
arr.add(i)
arr.add(targetNum / i)
}
}
}
return arr
} // End of divisor
private fun isAbundantNumber(targetNum: Int, arr: ArrayList<Int>): Boolean {
// 해당 값의 약수 배열을 새로 가져와야됨.
val size = arr.size
var sum = 0
for (i in 0 until size) {
if (arr[i] == targetNum) continue
sum += arr[i]
}
if (sum > targetNum) {
// 과잉수이면 true를 return
memo[targetNum] = 1
return true
}
if (sum == targetNum) {
memo[targetNum] = 3 // 완전수
} else {
memo[targetNum] = 2 // 부족수
}
return false
} // End of isAbundantNumber
