[SWEA] 활주로 건설

[문제]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH&

SW Expert Academy

[풀이]

 

 

제출일 : 2019-08-02 20:18

• C++언어
• 12,628 kb메모리
• 6 ms실행시간
• 1,694코드길이
• Pass결과

이 문제와 동일하다. 

2019/08/02 - [BOJ/삼성SW역량테스트] - [BOJ] 14890. 경사로

[BOJ] 14890. 경사로

 

---

#include <iostream>
#include <cstring>
#include <cmath>
 
using namespace std;
 
int n, x;
int map[20 * 2][20];
int ans;
 
void findPath(int r)
{
    int stand = map[r][0];
    int height[7];
    memset(height, 0, sizeof(height));
 
    height[stand] = 1;
 
    for (int i = 1; i < n; i++)
    {
        int next = map[r][i];
        //다음 칸 저장
        if (stand != next)
        {
            if (abs(stand - next) > 1)
            { //높이 차가 1 이상인 경우 -> 경사로 형성 불가
                --ans;
                return;
            }
            if (stand < next ) {
                //지금까지 지나온 높이가 같은 칸들이 x 이상이어야 한다. 
                if (height[stand] < x) {
                    --ans;
                    return;
                }
                height[stand] = 0;
                height[next] = 1;
            }
            else { //stand > next => 앞으로 지날 칸들 중 높이가 next와 같은 칸이 x이상 있어야 한다. 
                for (int j = i; j < i + x && j < n; j++) {
                    if (next == map[r][j]) {
                        height[next]++; //얼마나 많은 칸들이 같은지 저장해줌 
                    }
                }
                if (height[next] < x) {
                    --ans;
                    return;
                }
                height[next] -= x;
                i += x-1; //x칸 만큼 땡겨준다. 
            }
            stand = next;
        }
        else { //stand == next
            height[stand]++; //stand가 같은 경우 카운트를 증가해줌
        }
    } //for 열
}
void init()
{
    memset(map, 0, sizeof(map));
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
 
    cin >> t;
 
    for (int tc = 1; tc <= t; tc++)
    {
        cin >> n >> x; //격자판의 너비, 경사로의 길이
 
        ans = n * 2;
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> map[i][j];
            }
        }
 
        for (int i = n; i < n * 2; i++)
        {
            for (int j = 0; j < n; j++)
            {
                map[i][j] = map[j][i - n];
            }
        }
 
        for (int i = 0; i < n * 2; i++)
        {
            findPath(i);
        }
 
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}