백준) 우선순위 큐, DP

최대 힙 11279번

---

내가 떠올린 풀이 해설

이 문제는 단순히 우선순위 큐를 이용하면 해결할 수 있는 문제이다. 우선순위 큐의 Collections.reverseOrder를 이용하면 poll를 하면 배열에서 큰 숫자대로 출력된다. 0일 때 배열에서 제일 큰 수가 출력되도록 문제를 풀면 된다.

---

정확한 풀이

import java.util.*;
import java.io.*;
public class Baek11279 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());
		for(int i = 0; i < n; i++) {
			int m = Integer.parseInt(br.readLine());
			if(m != 0) {
				que.offer(m);
			}
			else {
				if(que.isEmpty()) {
					System.out.println(0);
				}
				else {
					System.out.println(que.poll());
				}
			}
		}
	}
}

---

Four Squares 17626번

---

내가 떠올린 풀이 해설

dp는 점화식을 떠올리는게 제일 어렵다. 제일 작은 수부터 계산을 해보면 1은 1개, 2 2개, 3 3개, 4  1개, 5  2개, 6  3개, 7  4개, 8  2개, 9  1개이다. 어떤 수 i의 최적의 해는 i 보다 작은 모든 제곱수 들 중 i - (제곱수)를 한 해 중 가장 작은 해에 1을 더한 값을 의미합니다. 그러면 점화식은 dp [i] = min(dp [i - j * j]) + 1 이렇게 작성할 수 있다. 작성한 점화식을 이용해 2중 for문을 이용해 풀면 답이 나오는 문제이다.

---

정확한 풀이

import java.util.*;
public class Baek17626 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] dp = new int[n + 1];
		dp[1] = 1;
		int min = 0;
		// 점화식 dp[i] = min(dp[i - j * j]) + 1
		for(int i = 2; i <= n; i++) {
			min = Integer.MAX_VALUE;
			for(int j = 1; j * j <= i; j++) {
				int tmp = i - j * j;
				min = Math.min(min, dp[tmp]);
			}
			dp[i] = min + 1;
		}
		System.out.println(dp[n]);
	}
}

---

오늘의 회고

오늘은 한주를 시작하는 월요일입니다. 이번 주도 열심히 공부하고 알고리즘 문제를 풀겠습니다. 벌써 제가 5월 13일에 퇴사하고 취업 준비한 지 2달이 지났습니다. 아직 부족한 것이 많은데 시간이 금방 지나갔습니다. 원래 퇴사하고 그전에 있던 회사에서 느낀 점 퇴사한 이유 취업준비에 대한 다짐을 쓴 글을 취업 준비하기 첫날에 쓰려고 했는데 쓰고 지우 고를 반복하다가 아직까지 작성하지 못했습니다. 취업 준비한 지 2달쯤 지났고 해이해진 정신상태를 다시 잡기 위해 다음 주 까지는 작성하겠습니다.