<백준> 가희와 탑(Gold 3)

[백준]

https://www.acmicpc.net/problem/24337

[깃허브]

ForCodeKata/baekjoon 문제집/24337 가희와 탑 at main · heesoo-park/ForCodeKata

제출 결

---

처음에는 문제를 보고 이전에 풀었던 탑 문제들이랑 비슷하겠구나 하고 더 내려가는데 갑자기 이걸 어떻게 풀어야하지? 라는 문제로 바꼈다.

그냥 보이는 건물을 찾는 게 아니라 보이는 건물 개수에 맞춰 그 건물들의 높이 정보를 출력해야했기 때문이다.

완전 반대 문제인 것이다.

 

그래서 스택문제일까 했지만 뭐 넣을 수 있는 것도 없고 이 방향이 아닌 것 같아 문제에 적혀져 있는 분류를 보니 그리디 알고리즘이었다.

그리디 알고리즘... 접근만 해서 쉽게 바꾼다면 아주 가볍게 풀 수 있는 문제라는 거였다.

하지만 그 방법이 떠오르지 않았고 참고하여 풀게 됐다.

 

일단 가희와 단비가 볼 수 있는 건물들의 수대로 건물들을 나열하는 걸 먼저 하기 시작했다.

가희가 볼 수 있는 개수가 a개라면 1 ~ a-1까지 건물들의 높이 정보를 저장하는 MutableList에 추가했다.

그리고 a 번째자리는 가장 높아야하는 건물이고 가장 높아야하는 건물은 가희와 단비 모두에게 가장 높은 건물이어야하기 때문에 a와 b 중에 더 큰 숫자로 넣어줬다.

이어서 b-1부터 1까지 쭉 넣어줬다.

이렇게 하면 가희와 단비가 볼 수 있는 건물들의 수대로 건물들을 나열한 것이 된다.

 

하지만 이렇게 했을 때 n보다 크다면 가능한 경우의 수가 없는 것이기 때문에 -1을 출력하고 프로그램을 종료한다.

(이 방식으로 안 하고 미리 a + b > n + 1보다 큰 지 체크해서 프로그램을 종료한다면 시간이 훨씬 빠르긴 하다.)

 

그 다음에는 a + b가 n보다 작은 경우를 처리해줘야한다.

사전순으로 가장 빠른 나열을 출력해야하기 때문에 생각할 수 있는 것은 남는 공간에 1을 맨 앞쪽으로 다 추가하는 것이다.

하지만 a가 1일 때는 무조건 1을 맨 앞으로 넣는 경우 a가 1이 아닌 2가 되는 경우가 생기면서 틀리는 케이스가 나오게 된다.

이에 대한 해결책은 아주 간단하다.

맨 앞이 아닌 그 다음 자리에 넣으면 된다.

그렇게 되면 가장 높은 건물 뒤에 1이 들어가게 되므로 가희가 바라볼 때는 1, 단비가 바라볼 때는 b가 그대로 나온다.

 

정말 그리디 알고리즘은 어떻게 문제를 해석하고 쉽게 풀어내느냐가 중요한 것 같다.

많은 문제를 접하는 게 중요하다.

이제 숫자를 사전순으로 빠른 걸 나열하시오 라고 나온다면 1을 최대한 앞에 쌓아버리자라는 생각이 들 거 같다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val sb = StringBuilder()
    
    val (n, a, b) = br.readLine().split(' ').map { it.toInt() }
    val buildings = mutableListOf<Int>()
    
    for (i in 1 until a) {
        buildings.add(i)
    }
    
    buildings.add(maxOf(a, b))
    
    for (i in b - 1 downTo 1) {
        buildings.add(i)
    }
    
    if (buildings.size > n) {
        print(-1)
        return
    }
    
    while (buildings.size < n) {
        if (a == 1) buildings.add(1, 1) else buildings.add(0, 1)
    }
    
    for (building in buildings) {
        sb.append("$building ")
    }
    print(sb)
}

 

참고)

https://velog.io/@dksekfbs72/%EB%B0%B1%EC%A4%80-24337%EB%B2%88-%EC%9E%90%EB%B0%94-%ED%92%80%EC%9D%B4