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

컴퓨터 이론/알고리즘

inspire12 2016. 9. 10. 18:57

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

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

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

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

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

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

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

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

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

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

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

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

정답

1. divide and conquer(재귀)

2. 스택 사용