백준 14890 경사로

작성일 | In |

Problem : 경사로

유형 : 시뮬레이션

문제, 예제, 출력 설명

링크로 대체합니다.

해결 전략

쉽게 문제를 풀기 위해, 단 방향으로만 탐색하게 했다.
기존의 board를 시계 방향으로 90도 돌린 후 아래에 붙였다.

연속된 평지의 개수를 따로 관리하며 경사로 설치 가능 여부를 확인했다.
오르막 경사로의 경우, 평지가 L개 있음을 확인하고,
내리막 경사로의 경우, 경사로가 겹치는 지의 여부를 확인했다.
내리막의 경우에는, 일단 우측에 충분한 평지가 있다고 가정하고 시작했다.
길의 탐색이 끝났을때, 경사로가 완전히 설치 되었을 경우에만 갈수 있는 길 이라고 하였다.

주의할 점

  • 변수로 두어야 할것을 상수로 두지말자.
    • 나의 경우 L을 예제의 상수로 설정해서 처음에 이상한 값이 나왔다.
  • 내리막 경사로를 설치할때, 길이 있다고 가정하고 시작할시
    • 내리막 경사로 설치의 시작점에서, 연속된 평지의 길이는 1 - L 이 되어야 한다.
    • 시작점도 경사로의 한 부분이기 때문이다.

풀이

단 방향으로만 탐색할 수 있도록 세팅한다.

  • 맵을 90도로 돌린 후, 밑에 이어붙인다.

각 행마다 길이 될 수 있는지 여부를 확인한다.

  • 가능하다면, 갈수 있는 길의 카운트를 증가시킨다.

경사로를 설치해나가며 길이 될 수 있는지를 확인한다.

  • 연속되는 평지의 개수를 계속 세어나간다
  • 높이가 두 칸 이상 차이 나면 불가능.
  • 오르막길인 경우
    • 평지가 경사로의 길이 이상 있어야 함. 모자르다면 실패
    • 성공한다면, 평지는 1개부터 다시 시작.
  • 내리막길인 경우
    • 이후에 평지가 경사로의 길이 이상 있어야 함
    • 평지가 있다고 가정하고 1 - 경사로의 길이 의 연속된 평지의 개수가 있다고 설정함.
    • 만약 내리막길을 만났는데, 현재 연속된 평지가 0보다 작은경우
      • 지금 내리막길을 만들며 내려가는 중임.
      • 내리막길은 겹칠 수 없으므로 실패.
  • 내리막의 경우, 평지가 있다고 가정 했다.
    • 끝낫을때, 평지가 음수개 있다면, 아직 경사로를 설치하는 중이다
    • 경사로를 완성하지 못했으므로, 실패

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;

int n, runway_len;
int board[204][102];

bool go_check(int i) {
    int before_h = board[i][0];
    int flat_cnt = 1;

    for (int ii = 1; ii < n; ++ii) {
        int cur_h = board[i][ii];

        if (before_h == cur_h) flat_cnt++;
        else if (abs(before_h - cur_h) > 1) return false;

        else if (before_h < cur_h) {
            if (flat_cnt < runway_len)  return false;
            flat_cnt = 1;
        }

        else if (before_h > cur_h) {
            if (flat_cnt < 0)   return false;
            flat_cnt = 1 - runway_len;
        }

        before_h = cur_h;
    }

    if (flat_cnt < 0)return false;
    else return true;
}

int solve() {
    int way_cnt = 0;
    for (int i = 0; i < n * 2; ++i) {
        if (go_check(i))    way_cnt++;
    }
    return way_cnt;
}

void init() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii) {
            board[n + i][ii] = board[(n - 1) - ii][i];
        }
    }
}

void input() {
    cin >> n >> runway_len;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii)  cin >> board[i][ii];
    }
    init();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    input();
    cout << solve();

    return 0;
}

피드백

문제를 어떻게 쉽게 풀수 있을까 고민하고 설계하는 능력이 중요하다.