타일의 개수는 1)마지막에 반드시 1을 사용하는 경우와 2)반드시 00을 사용하는 경우 2가지로 나눌 수 있는데, 이게 모든 경우의 수를 커버한다.
이것을 점화식으로 표현하면, a(n) = a(n-1) + a(n-2), 초기값은 a(1) = 1, a(2) = 2이 되는데,
a(n)은 타일의 개수가 n일 때, 만들 수 있는 모든 2진수의 가짓수를 의미한다.
피보나치랑 같은 식이 나와서 뭐지? 싶었는데 어이없게도 이게 맞다.
2번의 불필요한 계산을 줄이는 건, 탑다운 방식으로 풀 때는 메모이제이션 방식을, 바텀업 방식에서는 배열에 값을 저장해서 같은 문제의 답을 다시 구하지 않도록 해주면 된다.
이제 이것을 코드로 작성하면 놀랍도록 짧은 코드가 나오게 된다.
코드)
fun main(){
val n = readLine()!!.toInt()
val dp = IntArray(1_000_001) // 크기 n+1로 설정하면, n=1일 때 인덱스 에러 생겨요ㅠㅠ
dp[1] = 1; dp[2] = 2
for (i in 3..n){
dp[i] = (dp[i-2] + dp[i-1]) % 15746 // 점화식
}
println(dp[n])
}
수열의 합의 최대값을 구하는 문제이다. 숫자 2개를 위치에 관계 없이 묶거나 묶지 않고 더할 수 있으며, 묶을 경우엔 두 수를 곱해서 더해야 한다.
그냥 더하는 것보다 두 수를 곱할수록 합은 더 커진다. 그럼 어떻게 곱해야 더 크게 만들 수 있을까? 숫자 하나만 더한다고 생각했을 때, 가장 큰 수를 만드는 방법은 가장 큰 두 수를 곱하는 것이다. 즉, greedy하게 내림차순으로 큰 두 수씩 묶으면 값을 가장 크게 만들 수 있다.
음수인 경우엔 어떨까?
음수를 곱하면 양수가 되므로 마찬가지로 곱하는 게 항상 이득이다. 따라서, greedy하게 오름차순으로 절대값이 큰 두 수씩 묶으면 값을 가장 크게 만들 수 있다.
근데, 묶다가 마지막에 하나가 남는 경우가 생긴다. 양,음수 모두 홀수개일 때는 하나가 남는다.
음수의 경우 만약 0이 있다면 0과 곱하고, 0이 없다면 어쩔 수 없이 가장 작은 하나를 남겨둔다. 0을 곱하거나 양수와 곱하면 더 커질테니까.
양수는 남으면 그냥 더하는 수밖에 없다. 음수나 0이랑 곱하면 더 작이지기 때문이다.
즉, 0은남는 음수에 곱하는 용도로 사용한다. 음수와 곱하면 음수를 더 크게 만들 수 있지만 음수는 음수끼리 곱하는 것이 더 이득이기 때문이다.
Greedy)
이 문제는 위와 같이 greedy 방식으로 풀면 해결할 수 있다. 근데 위 방법대로 하면 정답을 받지 못한다ㅋㅋ! 0과 음수는 예외처리 했지만 1은 고려해주지 않았기 때문이다.
1은 어떤 수를 곱해도 자기 자신이 된다. 하지만 더한다면? (자기자신+1)이 된다. 1은 0과 곱하면 0으로 더 작아지고, 음수와 곱해도 작아진다. 따라서 1은 항상 묶지 않고 따로 더해줘야 한다. 1은 모두 따로 빼서 더하고 나머지 양수에 위의 방법을 적용하면 정답을 받을 수 있다.
위 방법을 정리하면 다음과 같다.
1. 수열을 입력 받는다 - 양수,음수를 따로 저장해준다. 0이 있는지 체크하고, 1은 모두 빼서 정답에 미리 더해준다.
2. 양,음 수열을 각각 정렬한다.
3-1 양의 수열)
개수가 0이면 0을, 1개면 그 원소를 정답에 더한다.
짝수개라면 크기순으로 2개씩 묶어서 곱한 것을 합해서 정답에 더한다.
홀수개이면 가장 작은 수와 나머지 짝수개를 묶은 것을 합해서 정답에 더해준다.
3-2 음의 수열) 양의 수열과 절대값에 대해 같은 방식으로 처리해준다
4) 음의 수열이 홀수개 && 0이 수열에 있다면, 더해줬던 가장 큰 음수를 정답에서 빼준다.
코드
fun main(){
var answer = 0
val n = readLine()!!.toInt()
val negatives = mutableListOf<Int>()
val positives = mutableListOf<Int>()
var hasZero = false
repeat(n){ i ->
val number = readLine()!!.toInt()
when{
number == 0 -> hasZero = true // 여러 개여도 상관없다
number == 1 -> answer++ // 바로 더해준다
number > 1 -> positives.add(number)
else -> negatives.add(number)
}
}
val numOfNegative = negatives.size
val numOfPositive = positives.size
positives.sort()
negatives.sortDescending() // 같은 함수로 처리하기 위해 내림차순 정렬
// 3)
answer += handleSequence(positives, numOfPositive) + handleSequence(negatives, numOfNegative)
// 4)
if (numOfNegative % 2 != 0 && hasZero){
answer -= negatives[0]
}
println(answer)
}
fun handleSequence(sequence: MutableList<Int>, numOfSequence: Int): Int{
return when{
numOfSequence == 0 -> 0
numOfSequence == 1 -> sequence[0]
// 2개씩 묶어서 곱한 것을 모두 더한다.
numOfSequence % 2 == 0 -> sequence.chunked(2).map{ it[0]*it[1] }.reduce{ sum, num -> sum + num }
else -> sequence[0] +
sequence.subList(1, numOfSequence)
.chunked(2)
.map{it[0]*it[1]}
.reduce{sum, num -> sum + num}
}
}
리뷰
처음에 그리디 문제인지 몰랐다. 그리디 문제는 딱 보고 눈치챌 수 있을 거라고 생각했는데, 앞으로 열심히 풀어야겠다..ㅋㅋ
그래프의 모든 노드를 인접한 노드와 같은 집합에 속하지 않도록 하면서, 두 집합으로 분할할 수 있는지 판별하는 문제이다.
먼저 노드를 두 집합으로 분할해야 하므로, 모든 노드를 방문하면서 어떤 집합에 속할 것인지를 정해준다. 분할하는 것을 쉽게 색칠한다고 표현하자. DFS나 BFS를 사용해서 노드를 한번씩만 방문하면서 인접 노드를 현재 노드와 다른 색으로 색칠하면 된다. 나는 colors라는 배열을 만들어서 모든 노드를 0과1로 나누었다.
얼핏 단순하게 "인접 노드를 모두 다른 색으로 칠하면 무조건 이분 그래프로 만들 수 있는 거 아닌가?"라고 생각할 수도 있지만, 인접노드가 이미 이전에 방문되었고, 현재 노드와 같은 색으로 칠해진 경우가 발생할 수 있다.
분할이 끝나면 그래프에서 모든 노드를 돌면서 자신과 같은 색인 인접노드가 있는지 확인해주면 이분 그래프인지 아닌지 판별할 수 있다.
참고로 연결 그래프라면 DFS나 BFS를 사용해서 노드를 한번씩만 방문하면서 이분 그래프 여부를 판별할 수 있으며, 연결 그래프가 아니라면 위에 언급한 대로 노드마다 인접 노드를 검사해주면 된다.
이를 좀 더 구체적으로 적으면 다음과 같다.
1. DFSorBFS를 사용해서 모든 노드를 한번씩 방문한다.
2. 노드마다 인접 노드와 다른 색으로 칠해준다.
3. 노드마다 인접 노드를 확인해서 같은 색으로 칠한 노드가 있으면 "NO", 없으면 "YES"를 출력한다.
코드
fun main(){
for(i in 0 until readLine()!!.toInt()){
var numberOfNode = 0
var numberOfEdge = 0
readLine()!!.split(" ").let{
numberOfNode = it[0].toInt()
numberOfEdge = it[1].toInt()
}
val visit = Array(numberOfNode){false}
val colors = Array(numberOfNode){-1}
val graph = Array(numberOfNode){mutableListOf<Int>()}
// 인접리스트로 그래프 저장
for(i in 0 until numberOfEdge){
readLine()!!.split(" ").map{it.toInt()-1}.let{
graph[it[0]].add(it[1])
graph[it[1]].add(it[0])
}
}
// DFS로 모든 노드 방문
(0 until numberOfNode).forEach { node ->
if (!visit[node]){
visit[node] = true
colors[node] = 0 // 첫 노드를 0으로 색칠
dfs(graph, node, visit, colors)
}
}
// 모든 노드마다 인접 노드가 무슨 색인지 확인한다
if (isBipartite(graph, colors)){
println("YES")
continue
}
println("NO")
}
}
fun isBipartite(graph: Array<MutableList<Int>>, colors: Array<Int>): Boolean{
graph.indices.forEach { node ->
graph[node].forEach { adjacent ->
if (colors[node] == colors[adjacent]){ // 현재 노드와 인접노드의 색이 같으면 false
return false
}
}
}
return true
}
fun dfs(graph: Array<MutableList<Int>>, node: Int, visit: Array<Boolean>, colors: Array<Int>){
graph[node].forEach { toNode ->
if (!visit[toNode]){
visit[toNode] = true
colors[toNode] = (colors[node]+1) % 2 // 인접노드를 현재 노드와 다른 색(0,1)으로 칠한다
dfs(graph, toNode, visit, colors)
}
}
}
조합마다 읽을 수 있는 단어 수를 구해서 정답과 비교한다. (앞 뒤 공통 글자들은 제외하고 확인)
풀이
알파벳 소문자로 구성된 n개의 단어 중에서, k개의 알파벳만 가지고 만들 수 있는 단어의 최대 개수를 구하는 문제이다.
(1<=n <=50, 0<=k<=26, 8<=단어 길이<=15)
완전 탐색)
여러 풀이 방법이 있는 것 같은데, 나는 모든 k개의 경우의 수를 살펴보는 완전 탐색 방법을 사용했다.
완전 탐색의 연산 횟수를 계산해보자. (1) 26개의 알파벳 중 k개의 경우의 수를 구해서 (2) 각 케이스마다 몇 개의 단어를 만들 수 있는지 확인해야는데, (3) 각 단어마다 어떤 알파벳들로 구성되어 있는지 확인해야 한다. 이를 계산해보면, 최대 연산 횟수는 (26C13) * 50 * 15 = 78억 번으로 1초 만에 통과할 수 없다.
그럼 어떻게 해야 할까?
문제의 조건에 따르면 남극의 모든 단어는 "anta"로 시작해서 "tica"로 끝나므로, 단어를 구성하기 위해선 'a', 'c', 'n', 't', 'i' 5글자는 반드시 포함해야 한다. 그럼 21개의 알파벳 중에서 k-5개의 경우의 수만 구하면 되므로, (21C10) * (15-8)(앞 뒤 네 글자 제외) * 50(단어 수) = 약 1.2억 번의 연산 횟수가 나온다. 나는 1초를 1억 번 정도의 연산으로 알고 있었는데, 요즘 컴퓨터는 1초에 10억 번은 거뜬히 계산한다고 한다. 그러니까 2억 6천 번 정도면 통과 가능한 수치라고 생각할 수 있다!
이제 지금까지의 과정에 따라 그대로 구현하면 정답을 찾을 수 있다. 나는 조합 함수를 재귀로 구현해서, k-5개의 알파벳 조합을 찾을 때마다 모든 단어를 확인했다. 그리고 그 조합으로 만들 수 있는 단어의 개수를 찾아서 기존의 최대 값과 비교하는 방식으로 구현했다.
또, n개의 단어를 Set으로 저장해서, 조합을 찾고 단어와 비교할 때 좀 더 빠르게 연산할 수 있도록 했다.
코드1
import kotlin.math.max
var answer = 0
var n = 0
var k = 0
val alphabets = ('a'.code..'z'.code).filter{ it.toChar() !in "antic" } // 5개 제외한 알파벳
fun main() {
readLine()!!.split(" ").let{
n = it[0].toInt()
k = it[1].toInt()
}
// 5개 미만의 글자로는 어떤 단어로 읽을 수 없다.
if (k < 5){
println(0)
return
}
val words = Array(n){setOf<Char>()} // 각 단어의 알파벳 set을 담는 배열
for (i in 0 until n){
words[i] = readLine()!!.toSet()
}
combine(words, 0, 0, "antic".toMutableList()) // 조합을 찾을 때마다 만들 수 있는 단어 개수 확인
println(answer)
}
fun combine(words: Array<Set<Char>>, startIdx: Int, combinationCount: Int, combination: MutableList<Char>){
if (k-5 == combinationCount){ // a,n,t,i,c를 제외하고 k-5개의 글자 조합을 찾으면
var count = 0
words.forEach { word -> // 현재 조합으로 단어를 만들 수 있는지 확인
if (combination.containsAll(word)){ // '=='으로 확인하면 조합의 글자 수가 더 많은 경우를 놓친다.
count += 1
}
}
answer = max(answer, count)
return
}
for (i in startIdx until 21){
combination.add(alphabets[i].toChar())
combine(words, i+1, combinationCount+1, combination)
combination.removeAt(5+combinationCount) // 조합에 기본적으로 5개 글자가 들어있음
}
}
코드2
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max
val srcLetters = mutableListOf<Char>()
var numOfPick = 0
lateinit var pickedLetters: MutableSet<Char>
lateinit var setsOfWords: Array<MutableSet<Char>>
var answer = 0
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val (numOfWords, numOfLetters) = readLine().split(" ").map(String::toInt)
if (numOfLetters == 26) {
println(numOfWords)
return
} else if (numOfLetters < 5) {
println(0)
return
}
val fixedLetters = arrayOf('a', 'n', 't', 'i', 'c')
numOfPick = numOfLetters - 5
setsOfWords = Array(numOfWords){ HashSet() }
pickedLetters = HashSet()
repeat(numOfWords) { setIndex ->
val word = readLine()
for (i in 4 until word.length - 4) {
if (word[i] !in fixedLetters) {
setsOfWords[setIndex].add(word[i])
}
}
}
for (ch in 'b'..'z') {
if (ch !in fixedLetters) {
srcLetters.add(ch)
}
}
pick(0, 0)
println(answer)
}
fun pick(count: Int, startIndex: Int) {
if (count >= numOfPick) {
val readCount = getHowManyRead()
answer = max(answer, readCount)
return
}
// 앞으로 뽑아야 할 문자 수 > 남아있는 문자 수
if (numOfPick - count > 21 - startIndex) {
return
}
for (i in startIndex until 21) {
pickedLetters.add(srcLetters[i])
pick(count + 1, i + 1)
pickedLetters.remove(srcLetters[i])
}
}
fun getHowManyRead(): Int {
var count = 0
for (word in setsOfWords) {
if (isReadable(word)) count++
}
return count
}
fun isReadable(word: Set<Char>): Boolean {
for (ch in word) {
if (ch !in pickedLetters) return false
}
return true
}
리뷰
시간 복잡도 계산하는 게 좀 거부감이 느껴진다. 그렇게 무시하고 풀다가 결국 시간 초과라는 걸 마주하게 된다. 익숙해져야지.
무시할 수 있는 문제 조건 같은 건 없다. 예를 들면 antic이라던지, antic이라던지..ㅠㅠ