초니로그

문제 URL

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

문제 설명 요약

• n개의 네모 모양 벽돌 정보가 주어짐
• 주어진 정보는 '밑면의 넓이'와 '높이' 그리고 '무게'
• 구해야 하는 것은 주어진 벽돌들 중 높이가 최대가 되도록 쌓을 때, 쓰인 벽돌의 개수와 각 벽돌의 순서
  (단, 순서를 출력할 때에는 제일 위에 쌓인 벽돌의 순서부터 출력해야함)
• 벽돌을 쌓을 때의 규칙은 아래와 같음
  
  1. 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
  2. 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
  3. 벽돌들의 높이는 같을 수도 있다.
  4. 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
  5. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다

문제 풀이

• 벽돌을 쌓을 수 있을지 없을지를 결정하는 요소가 '밑면의 넓이'와 '무게'이므로, 우선 둘 중에 하나를 기준으로 배열을 정렬해둠
• 정렬 이후 Dynamic Programming(동적 계획법)을 활용하여, 쌓을 수 있는지 없는지에 대한 판단을 요소별로 쪼개어 수행

Swift를 활용한 풀이

import Foundation

let n = Int(readLine()!)! // 벽돌의 개수
var origin:[[Int]] = [] // 벽돌들의 정보

// 벽돌 정보 입력 받기
for _ in 0..<n {
    origin.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}
// 벽돌의 밑면의 넓이를 기준으로 내림차순 정렬
var sorted_list = origin.sorted { $0[0] > $1[0] }

var dy:[Int] = [] // 높이합 최대 기록 배열
var hist:[Int:[Int]] = [:] // 각 항목 별 쌓을 수 있는 벽돌의 무게 정보 - [s:[w1, w2, ...]]

// 밑면이 가장 넓은 벽돌(맨 앞의 벽돌)에 대한 정보는 기본적으로 저장 (비교 대상이 없기 때문)
dy.append(sorted_list[0][1])
hist[sorted_list[0][0]] = [sorted_list[0][2]]

// 최대값에 관한 정보는 모두 밑면이 가장 넓은 벽돌(맨 앞의 벽돌)의 값으로 초기화
// (0과 빈 배열로 초기화해두면, 0번째 값을 고려하는 경우가 없어지기 때문)
var max_h_sum = dy[0] // 높이 합의 최대값
var max_h_list:[Int] = hist[sorted_list[0][0]]! // 높이 합이 최대인 경우의 높이값 요소 배열

// 2번째 벽돌 정보부터 살펴보면서, 이전 벽돌 중 자신이 위에 쌓일 수 있을지를 판단
for i in 1..<n {
    var max_h = 0
    var temp:[Int] = []
    for j in (0..<i).reversed() {
        // 이전 벽돌 중 자신보다 무게가 무거운 벽돌이면서, 높이의 합이 최대치인 경우의 정보를 임시 저장
        if (sorted_list[i][2] < sorted_list[j][2] && dy[j] > max_h) {
            max_h = dy[j]
            temp = hist[sorted_list[j][0]]!
        }
    }
    // 바로 위 for문에 의해 결정된 '높이의 합이 최대이면서, 무게가 자기자신보다 무거운 벽돌'의 정보를 기반으로 dy와 hist 초기화
    temp.append(sorted_list[i][2])
    hist[sorted_list[i][0]] = temp
    dy.append(max_h + sorted_list[i][1])

    // dy와 hist의 정보가 추가될 때마다, 각 높이의 합과 그것을 이루는 높이 요소값 배열을 갱신
    if (max_h_sum < dy[i]) {
        max_h_sum = dy[i]
        max_h_list = hist[sorted_list[i][0]]!
    }
}

// 결정된 최대 높이값의 요소 배열을 뒤집고 출력
// (무게를 기준으로 내림차순 된 배열에서 값을 찾았기때문)
max_h_list = max_h_list.reversed()
print(max_h_list.count)
for w in max_h_list {
    for i in 0..<origin.count {
        if(origin[i][2] == w) { print(i+1) }
    }
}