BOJ 14890. 경사로
14890번: 경사로
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
www.acmicpc.net
이번 문제는 처음에 갈피를 못잡아서 시간이 많이 걸렸던 문제다.
문제 아래에 힌트가 있으니 여기서 아이디어를 얻어가면 된다.
그런데, 문제에서 빠진 조건이 하나 있다
바로 가로 세로 경사로를 겹칠 수 있다는 것.
예를 들어 n이 4이고 l이 2인 상황에서
0 3 0 0
2 2 2 3
3 2 2 2
0 2 0 0
위와 같은 경우 세로로 경사로를 놓으면 높이를 표시했을 때 다음과 같다.
0 0 0 0
0 2 0 0
0 1 0 0
0 0 0 0
가로로 경사로를 놓게 되면 다음과 같다.
0 0 0 0
0 1 2 0
0 2 1 0
0 0 0 0
즉 세로로 경사로를 놓지 않으면 답이 2고, 그렇지 않으면 답이 1이 된다
그러나 문제에서는 이러한 경우를 고려하지 않는다는게 힌트를 통해 유추할 수 있다.
따라서 각 레인에 독립적으로 경사로를 놓고 판단하면 되는 문제이다.
풀이
1. 2차원 배열을 가로, 세로로 총 2n번으로 나눈다.
2. 나눈 배열들에 대해서 경사로를 놓고 지나갈 수 있는지를 판별한다.
시간복잡도
N = 100 이므로
O(n)=(한번 돌리는 시간)*(경사로 놓기)*(지나가기) = (100*100)*100*100 = 100,000,000
최악의 경우 약 0.5초 정도에 통과가 가능하다
나는 경사로를 놓는것을 최대한 O(n)에 하기 위해 다음과 같이 짰다
1. 배열을 읽으며 이전 값과 같으면 count += 1
2. 이전 값보다 다음 값이 크면 count가 l보다 클 때 경사로 놓기
3. 이전 값보다 다음 값이 작으면 작다는 것을 기록하고 count가 l보다 커질 때 경사로 놓기
이때 주의할 점은 l이 1인 경우를 고려해야 하며, 문제에서 주어진 예시들을 잘 활용해야 한다
