1. ๋ฌธ์ ์ ๋ํ์ฌ ๐ฆ
- ๋ฌธ์ ๋งํฌ: https://www.acmicpc.net/problem/17420
(1) ์กฐ๊ฑด ๋ถ์ ๐
๊ธฐํํฐ์ฝ๋ง๋ค ์ฌ์ฉ ๊ธฐํ๊ณผ ์ฌ์ฉ ๊ณํ์ผ์ด ์๋ค.
- ๊ธฐํํฐ์ฝ์ ๋ฌด์กฐ๊ฑด ์ฌ์ฉ ๊ณํ์ผ ์์๋๋ก ์จ์ผ ํ๋ค.
- ์ฌ์ฉ ๊ธฐํ์ 30์ผ ์ฉ ๊ณ์ ์ฐ์ฅํ ์ ์๋ค.
- ๊ธฐํํฐ์ฝ์ ์ฌ์ฉํ ๋ ํด๋น ๊ธฐํํฐ์ฝ์ ๋ฌด์กฐ๊ฑด ์ฌ์ฉ๊ธฐํ์ด ์ ์ผ ์งง์์ผ ํ๋ค.
- ์ฌ์ฉ ๊ณํ์ผ์ด ๊ฒน์น๋ฉด์ ์ฌ์ฉ ๊ธฐํ๋ ๊ฒน์น๋ ๊ฒฝ์ฐ ์๋ฌด๊ฑฐ๋ ์จ๋ ๋๊ณ , ๊ทธ๋ ๋ณต์๋ก ์ฌ๋ฌ ๊ฐ ์ฌ์ฉํด๋ ๋๋ค.
์ด๋, ๊ธฐํํฐ์ฝ์ ์ฐ์ฅ์ ์ต์๋ก ํ๋ฉด์ ๋ชจ๋ ๊ธฐํํฐ์ฝ์ ๊ณํ์ผ์ ์ฌ์ฉํ๋ ค๊ณ ํ๋ค. ์ฐ์ฅ ์ต์ ํ์๋ ์ด๋ป๊ฒ ๋๋๊ฐ?
2. ์ฝ๋๊ฐ ๋์ค๊ธฐ๊น์ง ๐ ๏ธ
KEY WORD: ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ, ์ ๋ ฌ, ์ฐ์ ์์ ํ
๊ธฐํํฐ์ฝ์ ์ฌ์ฉ ๊ธฐํ์ ๋ค์๊ณผ ๊ฐ์ ์์น์ ์ง์ผ์ผ ํ๋ค.
- ์ต์ํ ์์ ์ ์ฌ์ฉ ๊ณํ์ผ๋ณด๋จ ์ฌ์ฉ ๊ธฐํ์ด ๊ธธ์ด์ผ ํ๋ค.
- ๊ณผ๊ฑฐ ๋ ์ง์ ์ฌ์ฉํ ๊ธฐํํฐ์ฝ ์ค ์ฌ์ฉ ๊ธฐํ์ด ๊ฐ์ฅ ๊ธด ๊ฒ๋ณด๋ค ์ฌ์ฉ๊ธฐํ์ด ๊ธธ์ด์ผ ํ๋ค.
1๋ฒ์ ๋น์ฐํ ์๋ฆฌ์ด๊ณ , 2๋ฒ์ ๋ํด์ ์ง๊ณ ๋์ด๊ฐ๊ฒ ๋ค.
(1) ์ด์ ๋ ์ง์ ์ต์ฅ ๊ธฐํ ๊ธฐํํฐ์ฝ๋ณด๋ค ์ฌ์ฉ ๊ธฐํ ๊ธธ์ด์ผ ํจ.
ํ ๋ ์ง์ ์ฌ์ฉํ๋ ๊ธฐํํฐ์ฝ์ A๋ผ๊ณ ํด๋ณด์. A๋ฅผ ์ฌ์ฉํ๋ ์์ ์ A๋ ๋ฏธ๋ ์์ ์ ์ฌ์ฉํ ์ด๋ ๊ธฐํํฐ์ฝ๋ณด๋ค ์ฌ์ฉ๊ธฐํ์ด ์งง์์ผ ํ๋ค. ๊ธฐํํฐ์ฝ์ ์ฌ์ฉ ๊ธฐํ์ ์ถ์ํ ์ ์์ผ๋ฏ๋ก, ์ด๋ A๋ณด๋ค ๊ธฐํ์ด ์งง์ ๋ฏธ๋์ ์ฐ๋ ๊ธฐํํฐ์ฝ์ A๋ณด๋ค ๊ธธ๊ฒ ์ฐ์ฅํด์ผํจ์ ์ ์ ์๋ค.
์ด๋ ์ค์ํ ๊ฒ์ ์ด์ ๋ ์ง๋ผ๋ ๊ฒ์ด๋ค. ๋์ผ ๋ ์ง์ ํจ๊ป ์ฐ๋ ๊ธฐํํฐ์ฝ๋ค ๋ผ๋ฆฌ์ ๊ฒฝ์ฐ, ์ฌ์ฉ๊ธฐํ์ด ์งง์ ์์ผ๋ก ๊ทธ ๋ ์ฐ์ํด์ ์ฐ๋ฉด ๋๋ฏ๋ก, ์๋ก ๊ธฐํ์ ๋๋ ค์ค ํ์๊ฐ ์๋ค.
์๋ฅผ ๋ค์ด ๋ค์๊ณผ ๊ฐ๋ค๊ณ ํด๋ณด์.
"๊นํฐ 1": (๊ธฐํ: 24, ์ฌ์ฉ ๊ณํ์ผ: 25),
"๊นํฐ 2": (๊ธฐํ: 2, ์ฌ์ฉ ๊ณํ์ผ: 30),
"๊นํฐ 3": (๊ธฐํ: 3, ์ฌ์ฉ ๊ณํ์ผ: 30),
"๊นํฐ 4": (๊ธฐํ: 29, ์ฌ์ฉ ๊ณํ์ผ:30),
"๊นํฐ 5": (๊ธฐํ: 25, ์ฌ์ฉ ๊ณํ์ผ:35)
๋จผ์ ๊นํฐ1์ ์จ์ผ ํ๋ค. ํ์ง๋ง, ์์ ์ ์ฌ์ฉ ๊ณํ์ผ๋ณด๋ค ๊ธฐํ์ด ์งง๊ณ , ๋ฟ๋ง ์๋๋ผ ๋๋จธ์ง ๊นํฐ์ ๋น๊ตํ์ฌ๋ ๊ธฐํ์ด ์ ์ผ ์งง์ง ์๋ค. ๋ฐ๋ผ์ ์์ ์ ๊ธฐํ์ 30์ผ ์ฐ์ฅํจ๊ณผ ๋๋ถ์ด ๋๋จธ์ง ๊นํฐ๋ ์ ๋ถ ์ฐ์ฅํด์ผ ํ๋ค.
"๊นํฐ 1": (๊ธฐํ: "54", ์ฌ์ฉ ๊ณํ์ผ: 25), // 1๋ฒ ์ฐ์ฅ
"๊นํฐ 2": (๊ธฐํ: "62", ์ฌ์ฉ ๊ณํ์ผ: 30), // 2๋ฒ ์ฐ์ฅ
"๊นํฐ 3": (๊ธฐํ: "63", ์ฌ์ฉ ๊ณํ์ผ: 30), // 2๋ฒ ์ฐ์ฅ
"๊นํฐ 4": (๊ธฐํ: "59", ์ฌ์ฉ ๊ณํ์ผ:30), // 1๋ฒ ์ฐ์ฅ
"๊นํฐ 5": (๊ธฐํ: "55", ์ฌ์ฉ ๊ณํ์ผ:35) // 2๋ฒ ์ฐ์ฅ
๋จผ์ ๊นํฐ1์ 30์ผ ์ถ๊ฐํ์ฌ 1๋ฒ ์ฐ์ฅํ ๋ค์ ๋๋จธ์ง ๊นํฐ๋ค์ 54์ผ๋ณด๋ค ๋ ๊ธธ๊ฒ ๊ธฐํ์ ์ฐ์ฅํ๋ค. ์ดํ ๊นํฐ1์ ์ฐ๋ฉด ๋๋จธ์ง ๊นํฐ 2 ~ 5 ๊น์ง ์จ์ผ ํ๋๋ฐ, ๊นํฐ 2~4 ๊น์ง๋ ์ฌ์ฉ ๊ณํ์ผ์ด ๊ฐ์์ ์ ์ ์๋ค.
๋ง์ฝ ์์ ์ ํ ์์๋๋ก ๊นํฐ๋ฅผ ์ด๋ค๋ฉด ๋ง์ง๋ง ๊นํฐ4๋ 63๋ณด๋ค ๊ธฐํ์ด ๊ธธ์ด์ผ ํ๊ธฐ์ ํ ๋ฒ ๋ ์ฐ์ฅํด์ผ ํ๊ณ , ์ด์ ๋ฐ๋ผ ๊นํฐ 5๋ ์ฐ์์ ์ผ๋ก ์ฐ์ฅํด์ผํ๋ค. ์ด๋ฏธ ์ด๊ฒ์ ์ต์ ์ฐ์ฅ ํ์๋ณด๋ค ๊ธธ์ด์ง์ ์ ์ ์๋ค.
๊ฐ์ ๊ณํ์ผ์ ๊นํฐ์ ๋ํด์๋ ๋ค์ ์ ๋ ฌํด์ผ ํ๋ค.
"๊นํฐ 4": (๊ธฐํ: "59", ์ฌ์ฉ ๊ณํ์ผ:30),
"๊นํฐ 2": (๊ธฐํ: "62", ์ฌ์ฉ ๊ณํ์ผ: 30),
"๊นํฐ 3": (๊ธฐํ: "63", ์ฌ์ฉ ๊ณํ์ผ: 30),
"๊นํฐ 5": (๊ธฐํ: "55", ์ฌ์ฉ ๊ณํ์ผ:35)
์ด๋ฌ๋ฉด 30์ผ์๋ ์ฟ ํฐ ์ฐ์ฅ ์์ด ๋น์ผ ์ฟ ํฐ์ ๋ชจ๋ ์ธ ์ ์๋ค.๊นํฐ 5๋ ์์ ๋ณด๋ค ์ด์ ๋ ์ง ๋ชจ๋ ๊นํฐ๋ณด๋ค ๊ธฐํ์ด ๊ธธ์ด์ผ ํ๋ค. ์ฆ ์ ์ผ ๊ธฐํ์ด ๊ธธ์๋ 63๋ณด๋ค ๊ธธ์ด์ผ ํ๋ฏ๋ก ํ ๋ฒ ๋ ์ฐ์ฅํ๋ค.
"๊นํฐ 5": (๊ธฐํ: "85", ์ฌ์ฉ ๊ณํ์ผ:35) // 1๋ฒ ๋ ์ฐ์ฅ
(2) ๊ตฌํ ๋ฐฉ๋ฒ
๊ทผ๋ฐ ๊ธฐํํฐ์ฝ์ด ์ด $100,000$ ๊ฐ์ฌ์ ์ด์ค ๋ฐ๋ณต๋ฌธ์ ํ ์ ์๋ค. ๊ทธ๋ ๊ธฐ์ ์์ ๊ฐ์ด ๊ฐ์ ์ฌ์ฉ ๊ณํ์ผ ๊นํฐ๋ฅผ ๋ชจ์ ์ฌ์ ๋ ฌ ๊ฐ์ ์์ ์ ํ ์ ์๋ค. ๋ฐ๋ผ์ ๊ตฌํ ์ ์๊ฐํด์ผํ ์ ์ ํ ๋ฒ์ ์ํ๋ก ๋ชจ๋ ๊ณ์ฐ์ด๋ค.
A. ์ธํ
์ฐ์ ์์ ํ๋ฅผ ๋ง๋ค๊ณ ๋ค์๊ณผ ๊ฐ์ด ์ ๋ ฌํ๋ค.
- ์ฌ์ฉ ๊ณํ์ผ์ด ์ด๋ฅธ ์์ผ๋ก ์ ๋ ฌ
- ์ฌ์ฉ ๊ณํ์ผ์ด ๊ฐ๋ค๋ฉด ์ฌ์ฉ ๊ธฐํ์ด ์งง์ ์์ผ๋ก ์ ๋ ฌ
B. ์ด์ ๋ ์ง ๊นํฐ ์ต๋ ๊ธฐํ vs ํ ๊นํฐ ์ฌ์ฉ ๊ณํ์ผ ์ค max
ํ์ฌ ๊นํฐ์ ์ฌ์ฉ ๊ธฐํ์ ๋๋ฆด ๋๋ ์ด์ ๋ ์ง ๊นํฐ์ ์ต๋ ๊ธฐํ๊ณผ ํ ๊นํฐ์ ์ฌ์ฉ ๊ณํ์ผ ์ค ์ต๋๊ฐ๋ณด๋ค ํฌ๊ฒ ๋๋ ค์ค์ผ ํ๋ค. ์ด๋ฏธ ์ด ๋๋ณด๋ค ํฌ๋ค๋ฉด ๋ฐ๋ก ๊ณ์ฐํ ํ์ ์๋ค.C. ๊ธฐํ์ด ๋์ผํ ๊ตฌ๊ฐ ํ์ธ
๋ค์ ๋ ๋ณ์๋ฅผ ์ธํ ํด์ ์ด์ฉํ๋ค. prev_max: ์ด์ ๊ตฌ๊ฐ ๊นํฐ๋ค ์ค ์ต์ฅ ์ฌ์ฉ ๊ธฐํsection_max: ํ์ฌ ๊ตฌ๊ฐ ๊นํฐ๋ค ์ค ์ต์ฅ ์ฌ์ฉ ๊ธฐํ
์ฐ์ ์์ ํ์ ๊นํฐ๋ฅผ ๋ฌดํ๋ ์ฌ์ฉ๊ธฐํ์ผ๋ก ํ๋ ๋ฃ์ด๋๋ค. -> NULL POINTER ERROR ๋ฐฉ์ง์ฉ
- ํ์ฌ ํ์ธ ์ค์ธ ๊นํฐ์ ๋ค์์ ํ์ธํ ๊นํฐ์ ์ฌ์ฉ ๊ณํ์ผ์ด ๊ฒน์น๋์ง ํ์ธํ๋ค.
- ๋ง์ฝ ๊ฐ๋ค๋ฉด, ๋์ผ ๊ตฌ๊ฐ์ด๋ฏ๋ก
section_max๋ง ์ ๋ฐ์ดํธ - ๋ง์ฝ ๋ค๋ฅด๋ค๋ฉด,
prev_max๋ฅผsection_max๋ก ๊ฐฑ์ ํ๋ค.
- ๋ง์ฝ ๊ฐ๋ค๋ฉด, ๋์ผ ๊ตฌ๊ฐ์ด๋ฏ๋ก
์ฌ๊ธฐ์ prev_max๊ฐ B์์ ํ์ธํ๋ ์ด์ ๋ ์ง ๊นํฐ ์ต๋ ๊ธฐํ์ด๋ค.
(3) ์๊ฐ๋ณต์ก๋ ๋ถ์ โณ
ํ ๋ฒ์ ์ํ์์ ๊ณ์ฐํ๋ฏ๋ก ์ต์ข $O(100,000)$ ์ด๋ค.
3. ์ฝ๋ ๐
(1) SUDO CODE ๐ฌ
+ 1. ์ฐ์ ์์ ํ (์ฌ์ฉ ๊ณํ์ผ ์ค๋ฆ์ฐจ์, ์ฌ์ฉ ๊ธฐํ ์ค๋ฆ ์ฐจ์) ๋ง๋ค์ด์ ๋ชจ๋ ๊ฐ ์ง์ด๋ฃ๊ธฐ
- (1) ๋ฌดํ๋ ์ฌ์ฉ ๊ธฐํ์ ๊ฐ์ง๋ ๋๋ฏธ ๊ธฐํํฐ์ฝ๋ ์ฐ์ ์์ ํ์ ๋ฃ๊ธฐ (null pointer ๋ฐฉ์ง)
+ 2. ์ฐ์ ์์ ํ์์ N๊ฐ ๋นผ๋ฉฐ ๋ค์์ ๋ฐ๋ณต
- (1) ์ด์ ๋ ์ง ๊นํฐ ์ค ์ต์ฅ ์ฌ์ฉ ๊ธฐํ๊ณผ ํ ๊นํฐ์ ์ฌ์ฉ ๊ณํ์ผ ์ค ์ต๋๊ฐ ๊ตฌํ๊ธฐ
- (2) ((1)์์ ๊ตฌํ Max๊ฐ - ํ ๋ ์ง ๊นํฐ ์ฌ์ฉ ๊ธฐํ) ๋งํผ ํ ๊นํฐ ์ฌ์ฉ ๊ธฐํ ์ฐ์ฅ
- ์ฐ์ฅํ ํ์๋ฅผ ๋ต์ ๋์
- (3) ๋ค์ ๊นํฐ๋ ํ ๊นํฐ์ ๊ฐ์ ์ฌ์ฉ ๊ณํ์ผ์ธ์ง ํ์ธ (๊ตฌ๊ฐ ํ์ธ)
a. ๋ค๋ฅด๋ฉด ํ ๊ตฌ๊ฐ์ ์ต์ฅ ๊ธฐํ์ผ๋ก ์ด์ ๊ตฌ๊ฐ ์ต์ฅ ๊ธฐํ ๊ฐฑ์
(2) JAVA CODE โ
import java.util.*;
import java.io.*;
// b 3109 ๋นต์ง
public class Main {
static class Gifticon{
int due;
int use_plan;
public Gifticon(int due, int use_plan){
this.due = due; // ์ฌ์ฉ๊ธฐํ
this.use_plan = use_plan; // ์ฌ์ฉํ ๊ณํ
}
@Override
public String toString(){
return String.format("(due: %d, use_plan: %d)", this.due, this.use_plan);
} } static int N;
static PriorityQueue<Gifticon> pq = new PriorityQueue<>((o1,o2) -> {
if(o1.use_plan == o2.use_plan) return o1.due - o2.due;
return o1.use_plan - o2.use_plan;
}); public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer dues = new StringTokenizer(br.readLine());
StringTokenizer dates = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++){
pq.add(new Gifticon(Integer.parseInt(dues.nextToken()), Integer.parseInt(dates.nextToken())));
} pq.add(new Gifticon(Integer.MAX_VALUE, Integer.MAX_VALUE));
int prev_max = 0;
int section_max = 0;
long answer = 0;
for(int i = 0; i < N; i++){
Gifticon now = pq.poll();
// ํ์ฌ ๊ฐ์ ๋ํ ๊ณ์ฐ
int minimum_due = Math.max(prev_max, now.use_plan); // ์ด์ ๊ตฌ๊ฐ ์ค ์ต๋ ๊ธฐํ vs ์์ ์ ๊ณํ์ผ ์ค ๋ ๋์ ๊ฒ
int extension_cnt = quotient(minimum_due - now.due ) + (remainder(minimum_due - now.due) != 0? 1 : 0);
answer += extension_cnt;
section_max = Math.max(section_max, now.due + extension_cnt*30);
// System.out.printf("%s, ์ฐ์ฅ ํ์: %d, ์ด์ ๊ตฌ๊ฐ ์ต๋๊ฐ: %d, ํ ๊ตฌ๊ฐ ์ต๋๊ฐ: %d\n", now, extension_cnt, prev_max, section_max);
// ๊ตฌ๊ฐ์ด ๋ฌ๋ผ์ง ๋,
if(now.use_plan != pq.peek().use_plan) {
prev_max = section_max;
} } System.out.println(answer);
}
public static int quotient (int target){
if(target <= 0) return 0;
return target/30;
}
public static int remainder (int target) {
if(target <= 0) return 0;
return target%30;
}
}
4. ํธ๋ฌ๋ธ ์ํ or ๋ฐฐ์ด ์ ๐
๋ฌธ์ ์ค๋ช ์ด ๋๋ฌด ๋ณ๋ก๋ค. ์ดํด๋ฅผ ์ด๋ฐ์ ๋ชปํ๋ค. ์๋๋ฉด ๋ฌธ์ ์์๋ ๊นํฐ ์ค ์ฌ์ฉ ๊ธฐํ์ด ์ ์ผ ์งง์ ๊ฒ๋ง ์ฌ์ฉํ๋ฉด ๋๋ค๊ณ ํ์ง, ๊นํฐ์ ์ฌ์ฉ๊ธฐํ์ ๊ทธ๊ฒ์ ๋ฌด์กฐ๊ฑด ์จ์ผ ํ๋ค๋ ์ด์ผ๊ธฐ๊ฐ ์์๊ธฐ ๋๋ฌธ์ด๋ค.