[백준]7344 나무 막대

문제소개

---

7344나무막대 문제는 LIS 문제이며 해당 문제는 2001년 ACM-ICPC 대전 기출 문제입니다. 

 

나무 막대기 가공 순서를 비교하는 문제로 비교 값은 길이와 무게 2개 입니다.

길이를 I, 무게를 W라고 하면 I <= I' , w <= w' 일 경우에만 준비 작업 없이 바로 작업을 이어 할 수 있습니다.

준비 작업이 필요한 경우는 +1이 발생하며 준비 작업을 최소화하는 문제 입니다.

즉, 길이와 무게가 작은 막대기부터 작업을 시작하여 길이와 무게가 큰 막대기 순으로 LIS를 생각하며 해결할 수 있습니다.

 

문제 풀이

---

 

idx	길이(I)	무게(W)
0	4	9
1	5	2
2	2	1
3	3	5
4	1	4

 

 

비교해야 하는 값이 2개입니다. 

비교를 간단하게 하기 위해서 길이를 기준으로 오름차순으로 정렬합니다.

 

 

Idx	길이(I)	무게(W)
0	1	4
1	2	1
2	3	5
3	4	9
4	5	2

 

길이가 정렬되어 있으므로 차례대로 무게만 비교하면 되며

모든 나무 막대기는 작업을 해야 하므로 0번 부터 차례대로 

무게를 비교하여 증가하는 막대기는 준비 작업없이 작업을 하는 것으로 표시합니다.

 

0 : (1,4) -> 2:(3,5) -> 3(4:9) 순서로 한 번의 준비 작업으로 처리할 수 있습니다.

그리디한 해결방법이네요.

---

소스보기