[BOJ] 2374번 같은수로 만들기

https://www.acmicpc.net/problem/2374

https://www.acmicpc.net/problem/13146

 

프로그래밍 문제를 접근할 때 가장 중요한건 문제를 단순화 시키는 것이다. 

이번 문제를 간단히 해보면 가장 낮은걸 수를 가장 높은 수와 같게 만드는 것이다.

이 때 연속된 이웃이 같으면 같이 올라가야한다는 조건이 붙는다

 

같은 수로 만들기는 두 가지로 풀었다.

 

위의 문제에서 첫번째는 재귀를 이용한 divide and conquer 접근했고

두번째 문제는 stack을 이용한 방법으로 접근했다. 

 

처음 떠오른 아이디어는 범위내(오름차순, 혹은 내림차순을 방해하는 걸로 짤라서)에서

가장 큰 수와 가장 작은 수를 맞추는 식으로(divide and conquer) 했고 첫번째 제약조건은 통과했다.

 

그런데 이 방법이 두번째 문제 같은 수로 만들기2로 가면 시간 초과가 걸린다. stack을 쓰는 식으로 최적화했다.

 

사실 두번째 stack을 쓰는 방법이 더 직관적이고 간단하며 시간도 빠르다.

stack, queue의 이론은 간단하지만 그걸 어디에 어떻게 쓰는지는 많이 겪어 봐야하는 것 같다.

 

 

 

------------

정답 

1. divide and conquer(재귀)

 https://github.com/inspire12/Algorithm/tree/master/acm13146github.com/inspire12/Algorithm/blob/master/acm2374/make_same_number1.cc

 

2. 스택 사용

https://github.com/inspire12/Algorithm/blob/master/acm13146/make_same_number2.ccgithub.com/inspire12/Algorithm/blob/master/acm13146/make_same_number2.cc