2022. 12. 14. 19:51ㆍ백준 & 프로그래머스
문제 보기
https://www.acmicpc.net/problem/15684
15684번: 사다리 조작
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선
www.acmicpc.net
풀이 과정
해당 문제는 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 |
'백준 & 프로그래머스' 카테고리의 다른 글
[백준] 13458번: 시험 감독 - python (0) | 2022.12.20 |
---|---|
[백준] 15686번: 치킨 배달 - 파이썬 (0) | 2022.12.15 |
[백준] 14890번: 경사로 - 파이썬 (0) | 2022.12.13 |
[백준] 14499번: 주사위 굴리기 - 파이썬 (0) | 2022.12.12 |
[백준] 13460번: 구슬 탈출 2 - 파이썬 (0) | 2022.12.11 |