boj 6198 옥상 정원 꾸미기 || 이 문제를 통해서, 예제가 제시해주는 형태로 답을 낼 필요가 없다는 것에 대해서 배움.

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

6198번: 옥상 정원 꾸미기

위의 문제에서, 설명을 해주는 부분에서 <관리인들이 옥상 정원을 확인할 수 있는 총 수는 3 + 0 + 1 +0 +1 + 0 = 5이다>

라고 설명을 하는데, 이렇게 숫자들이 나와서 더해야 하는 형태로 문제를 생각해버리면 구현하는데 있어서 오히려 로직에 제약을 받게 되는것 같다. 

결과적으로 사람이 보기에는 저런식으로 3개를 보고, 0개를 보고, 1개를 보고 , ... 1개를 보고, 0개를 보아서 합이 5개 이지만

이 문제에서 stack을 활용한 풀이를 할때는 스택에 점점 쌓이고, 그 전에 해당 순서의 높이 h를 볼 수 있는 수들을 스택에 남기게 되기 때문에, 각각의 순서에서 몇개의 기둥이 나를 보는지의 수의 합으로 이 문제를 해결할 수 있었다. 

그것을 문제에서 제시하는 예제로 그 풀이법에 대입해서 각각의 더하는 수들을 출력해보면, 

 

s.size() is : 0 (첫번째  기둥 10 이 자신보다 앞선 몇개의 기둥으로부터 관측되는지를 나타내는 숫자)
s.size() is : 1 (두번째 기둥 3 이 자신보다... 숫자)
s.size() is : 1 (세번째 기둥 7 이 자신보다... 숫자)
s.size() is : 2(네번째 기둥 4 이 자신보다... 숫자)
s.size() is : 0(다섯번째 기둥 12 이 자신보다... 숫자)
s.size() is : 1(여섯번째 기둥 2 이 자신보다... 숫자)

이와같은 형태로 stack에 수를 넣었다가 원하는 관계를 유지하는 수들을 남기고 pop을 하면서 그 남은 숫자들을 세는 풀이를 하기 때문에

위와같이 문제에서 제시한 예시와는 다른 값들의 합으로 정답 5를 도출한다. 

 

알고리즘 문제를 풀면서 예시에저 제시해주는 사람이 이해하는 논리로 문제를 해결하려고 하지 말자. 

결국에는 컴퓨터가 문제를 받아들이고 해결하는 형식으로 문제를 바라보고 해결해야 하기 때문에 제시해주는 예시와는 다를 수 있다. 

 

++++++++++++++=

일단 위의 풀이는 stack을 활용한 풀이에서의 방법이고, 

만약에 예시에서 제시해준대로 3 + 0 + 1 + 0 + 1 +  0 =5 형태로 수들이 나오게 하는 풀이를 만들 수 있는지, 만약 만들 수 있다면

어떤식으로 만들 수 있는지에 대해서는 한번 더 생각해보도록 하자.