/programmers

Tower 문제를 DP로 풀기

탑(Tower) 문제를 dynamic programming으로 풀기


프로그래머스의 레벨 2 스택/큐 문제인 탑 문제를 동적계획법으로 풀어보기

코딩테스트 연습 - 탑 | 프로그래머스
수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지…programmers.co.kr


큐/스택으로 푸는 것은 재미없기 때문에, DP를 사용하여 풀어야한다.

DP는 이전 답을 이용해서 다음 답을 구할 수 있을 때 사용할 수 있다.

이 문제에서는 각 탑이 자신의 신호를 수신할 타워를 기록해둠으로써 해결할 수 있다.

예를들어 heights = [6, 9, 5, 7, 4] 라면 우리가 목표로 하는 dp배열은 이렇게된다. 하나의 원소는 {idx, height}로 구성된다.

dp = [{0, 0}, {0, 0}, {2, 9}, {2, 9}, {4, 7}]

이 dp 배열이 있으면 답은 간단하게 구할 수 있다.

type tower struct {
idx int
height int
}
func solution(heights []int) []int {
dp := []tower{}
answer := []int{}
for i, v := range heights {
if i == 0 {
dp = append(dp, tower{0, 0})
answer = append(answer, 0)
continue
}
if heights[i-1] > v {
dp = append(dp, tower{i, heights[i-1]})
answer = append(answer, i)
} else {
var j int
for j = i - 1; j >= 0; j-- {
if dp[j].height > v {
j--
break
}
}
j++
dp = append(dp, tower{dp[j].idx, dp[j].height})
answer = append(answer, dp[j].idx)
}
}
return answer
}
view raw tower.go hosted with ❤ by GitHub

dp 배열을 구하는 것을 중점적으로 보면되는데,

앞의 타워가 클 경우 (16 줄)에 앞의 타워를 dp에 적어주고

그렇지 않을 경우에는 앞 타워들의 정답을 보면서 더 큰 타워가 나오면 그 답을 가져온다.

Jaeyoun

Jaeyoun

The maintainer

Read More