[백준] 15684번: 사다리 조작 - 파이썬

문제 보기

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

15684번: 사다리 조작

 

 

---

 

풀이 과정

해당 문제는 solved.ac의 골드 3에 랭크된 문제로 삼성 sw역량 테스트 기출 문제 중 하나이다!

우리가 자주 풀던 2차원 배열과 bfs, dfs를 이용한 문제이다. 먼저 변수의 범위를 살펴보자.

2 <= N <= 10, 1<= H <= 30 으로 그리 사이즈가 크지 않다. 또한 놓을 수 있는 가로 줄의 개수는 고작 3이다. 이 정도 크기면 푸는 방법은 간단하다! 단순하게 놓을 수 있는 모든 가로줄에 하나씩 넣으면서 3개를 넘지 않도록만 해주면 된다. 만일 이 방법으로 푼다면 브루스 포스가 된다.

 

 

하지만! 그래도 나름 코테와 알고리즘을 공부하는 사람으로서 브루스 포스는 영 맘에 들지 않는다ㅎㅎ 필자는 Greedy로 접근을 하였다.(사실 Greedy라는 표현이 맞을 지 모르겠다ㅎ) 전체 사다리의 값을 맞추기 위해서는 가장 자리 부터 맞춰야 한다. 그림으로 보면 이해가 더 쉬울 것이다! 

N이 3인 사다리가 있을 때 만일 가운데 값인 2를 먼저 맞춰준다면 위의 그림과 같이 흘러갈 것이다. 이후에 1이나 3을 맞추기 위해 또다시 2의 위치를 바꾸어 주어야 한다. 이는 무의미한 depth가 추가 되었다고 볼 수 있다. 그렇다면 가장자리를 먼저 맞추어 주자. 

 

해당 그림에서는 1을 먼저 맞추어 주었다. 그럼 이제 2와 3만 맞추어 주면 된다. 만일 3을 먼저 맞추어 주었어도 이는 1과 2만 맞추어 주면 된다. 즉 가장자리 부터 한 줄씩 최소 방법을 구해 맞춘 범위를 늘려가면 된다! 

 

또한 예시 문제에서 1의 결과값이 2번째 줄에서 나온다. 1의 결과값을 1에서 더 빠르게 찾기 위해서는 2번째보다 큰 줄에 가로줄을 추가하는 것보다 작은 줄에 가로줄을 추가해야 한다. 다시 말해 실행 결과로 나오는 값보다 작은 줄에 가로줄을 추가하는 것이 최솟값을 찾는 데 유리하다.

 

 

 

 

---

 

구현 방식 & 코드

필자는 구현 방식에서 삽질을 좀 했다ㅎ 사다리에서의 점을 이용해 2차원 배열에 Bool값을 넣어 구현을 하였다. 하지만 이렇게 구현할 경우 같은 가로줄에 1-2, 3-4 로 사다리를 설치할 경우 해당 가로줄이 모두 True가 되면서 사다리가 어떻게 연결된 것 인지 판단할 수 없었다.

True	True	False	False
False	False	True	True
False	True	True	False

 

 

따라서 Bool 값이 아닌 해당 점과 이어진 점의 x좌표 값을 넣어주었다! 따라서 세로줄의 인덱스와 해당 위치의 값이 다르다면 사다리가 설치 되어 있다는 의미이다.

 

1	0	2	3
0	1	3	2
0	2	1	3