Array ( )

2017 하반기 삼성 SW 역량 테스트 - 경사로

2018-12-12 01:37:10 | 조회수 5319



2017년 하반기 문제인 경사로 복원 문제입니다. 문제의 설명은 굉장히 길고 그림으로 자세히 설명되어 있어 이해하기 쉽습니다. 문제의 요지를 정리해보면 다음과 같습니다.


  • 현재 내가 서 있는 곳과 다음 가야할 곳의 높이 차이가 1보다 크면 갈 수 없다.
  • 높이 차이가 1일 경우 경사로를 놓아 갈 수 있는데, 경사로의 길이 L을 설치할 수 있는 땅이 있어야 한다.(중간에 높거나 낮으면 안된다.)
  • 경사로는 서로 겹칠 수 없으며, 바닥면이 항상 땅에 닿아야 한다.(2개의 경사로를 조립하여 사각형 등을 만들 수 없음)

이렇게 정리를 하고 보면, 결국 주어진 조건을 통해 모든 경로의 길을 다 갈 수 있는지 직접 진행을 해보며 문제를 푸는 시뮬레이션임을 알 수 있습니다. 구현을 진행해 봅시다.

먼저 높이가 1보다 넘게 차이가 나는 경우는 무조건 갈 수 없도록 처리해 줍니다. 다음에는 1 차이가 나는 내리막길 경사로, 오르막길 경사로의 2가지 경우가 존재하는데, 오르막길 경사로의 경우는, 같은 높이의 지나온 경로를 미리 세주면서 걷다가, 오르막길을 설치해야 할 때 자신이 지나온 길이 L과 같거나 더 길 경우 설치할 수 있도록 해주면 쉽게 구현할 수 있습니다. 내리막길의 경우, 내가 가야할 곳부터 길을 또 하나의 반복문으로 체크하여, L 이상의 길이 존재하는지 확인해 줍니다. 존재할 경우 경사로를 겹칠 수 없으므로, 내리막길을 내려간 다음 칸을 다음 대상으로 잡을 수 있도록 전처리를 해줍니다.


else if (now > board[i][j]) {

    int cnt = 0;

    for (int k = j; k < j + l; k++) {

        if (board[i][j] == board[i][k]) cnt++;

    }

    if (cnt != l) pass = false;

    j += l - 1;

    /*이하 생략*/

}


소스코드의 일부를 가져왔습니다. j += l-1을 해줌으로써, 다음 반복문 때 j++이 되어 최종적으로 l칸 만큼을 내려가게 되도록 구현하였습니다. 이렇게 해주면서 도착지점까지 문제 없이 도착했다면 길을 count 해주면 됩니다.


※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.

#include <iostream>
using namespace std;

int abs(int a) { return a < 0 ? -a : a; }
int main() {
    int n, l, t = 0, now, ans = 0, board[100][100];

    cin >> n >> l;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> board[i][j];

    for (int i = 0; i < n; i++) {
        now = board[i][0];
        t = 1;
        bool pass = true;
        for (int j = 1; j < n && pass; j++) {
            if (abs(board[i][j] - now) > 1) pass = false;
            else if (now > board[i][j]) {
                int cnt = 0;
                for (int k = j; k < j + l; k++) {
                    if (board[i][j] == board[i][k]) cnt++;
                }
                if (cnt != l) pass = false;
                j += l - 1;
                t = -1;
            }
            else if (now < board[i][j]) {
                if (t < l) pass = false;
                t = 0;
            }
            t++;
            now = board[i][j];
        }
        if (pass) ans++;
    }
    for (int i = 0; i < n; i++) {
        now = board[0][i];
        t = 1;
        bool pass = true;
        for (int j = 1; j < n && pass; j++) {
            if (abs(board[j][i] - now) > 1) pass = false;
            else if (now > board[j][i]) {
                int cnt = 0;
                for (int k = j; k < j + l; k++) {
                    if (board[j][i] == board[k][i]) cnt++;
                }
                if (cnt != l) pass = false;
                j += l - 1;
                t = -1;
            }
            else if (now < board[j][i]) {
                if (t < l) pass = false;
                t = 0;
            }
            t++;
            now = board[j][i];
        }
        if (pass) ans++;
    }
    cout << ans;
}


2017 하반기 삼성 SW 역량 테스트 - 경사로 - 알고리즘닷컴
32 개의 글