[백준 / Java] 2493번: 탑 (골드5)

문제 풀이 날짜: 2023.08.07
포스트 작성일: 2023.08.07

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 2493번: 탑 (골드5)

 

키워드

스택, 동적 계획법

 

풀이 접근법

• 브루트포스가 안 되는 이유 ⇒ 내림차순일 때 최악의 경우 시간복잡도가 O(n!)까지 나타날 수 있다.
• DP 배열에는 현재 위치한 i번째 탑에서 레이저가 닿는 가장 가까운 탑의 번호를 저장한다.
• 맨 첫번째 탑은 왼쪽으로 레이저가 닿는 탑이 하나도 없으므로 DP배열의 0번째 값은 0으로 초기화 한다.
  
  • 반복문을 순회하며 i번째와 i - 1번째 탑의 높이를 비교한다.
  • 만약 i - 1번째 탑이 i번째 탑보다 높다면, i번째 탑의 레이저가 i - 1번째 탑에 닿는 것이다. 따라서 DP배열에 i - 1번째 탑의 순서를 저장한다.
  • 만약 i - 1번째 탑이 i번째 탑보다 낮다면, i번째 탑의 레이저가 닿는 가장 가까운 탑을 찾아야 한다. i - 1번째 탑의 DP값을 기준으로 그보다 왼쪽에 i보다 높은 탑이 있는지 찾는다. 이는 가장 유망한 높이의 탑부터 탐색하는 것이다.
  • 만약 i - 1번째 탑의 DP값을 기준으로 찾지 않고 i - 1번째 탑의 높이부터 탐색한다면 시간 초과가 발생한다.
• 즉, 가장 유망한 탑으로부터 인덱스 j를 줄여가며 반복문을 순회하기 때문에 시간초과를 내지 않고 답을 찾을 수 있다.

 

코드

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		int[] towers = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			towers[i] = Integer.parseInt(st.nextToken());
		}

		int[] DP = new int[N];
		DP[0] = 0;
		for (int i = 1; i < N; i++) {
			if(towers[i] >= towers[i - 1]) {
				int start = DP[i - 1];
				
                	//현재 탑보다 높으면서도 가장 가까운 것을 찾는다.
				for(int j = start; j >= 0; j--) {
					if(towers[j] > towers[i]) {
						DP[i] = j + 1;
						break;
					}
				}
			}
			else { //towers[i] < towers[i - 1]
				DP[i] = i;
			}
		}

		StringBuilder sb = new StringBuilder();
		for (int dp : DP) {
			sb.append(dp).append(" ");
		}

		System.out.println(sb);
	}
}

---

 

git 링크

https://github.com/jinju9553/23-CodingTest/commit/892fa83dcd931e182c45f31a53d5c028fe38f388