백준 c++ 14890 "경사로" -PlusUltraCode-

https://www.acmicpc.net/problem/14890

 

 

 

 

 

 

[필자 사고]

구현 문제이다.

총 4가지의 경우의 수를 판단해야 된다.

 

1. 가로 행이 모두가 높이가 같을때

2. 가로 행 높이차가 2이상일 때

3. 오른쪽방향으로 경사가 질 때

4. 왼쪽 방향으로 경사가 질 때

 

1,2 번을 먼저 코드로 작성하여 1번과 2번 case 가 아닌경우 즉 3,4번만 판단하게 코드를 작성했다.

 

[문제 풀이]

 

경사로 설치 가능성 확인 함수들

1. isDifTwo: 연속된 두 칸의 높이 차이가 2 이상인 경우를 확인합니다.
2. isAllSame: 모든 칸의 높이가 같은 경우를 확인합니다.
3. leftRight: 왼쪽에서 오른쪽으로 경사진 경우

bool isDifTwo(vector<vector<int>>& map, int sero) {
    for (int i = 0; i < N - 1; i++) {
        int dif = map[sero][i] - map[sero][i + 1];
        if (abs(dif) >= 2) return true;
    }
    return false;
}

bool isAllSame(vector<vector<int>>& map, int sero) {
    for (int i = 0; i < N - 1; i++) {
        if (map[sero][i] != map[sero][i + 1]) return false;
    }
    resultCount++;
    return true;
}

int leftRight(vector<vector<int>>& map, int sero, int garo) {
    int beforeLoad = 1;
    if (beforeLoad == L) {
        return garo;
    }
    if (garo == N - 1) return -1;
    for (int i = garo; i < N - 1; i++) {
        if (map[sero][i] == map[sero][i + 1]) {
            beforeLoad++;
        } else {
            return -1;
        }
        if (beforeLoad == L) {
            return i + 1;
        }
    }
    return -1;
}

경사로 설치 함수

지형을 순회하며 경사로 설치가 가능한지 확인하고, 가능하면 resultCount를 증가시킵니다.

 

void makeGame(vector<vector<int>>& map) {
    for (int i = 0; i < N; i++) {
        if (isAllSame(map, i)) continue;
        if (isDifTwo(map, i)) continue;
        
        bool flag = true;
        int beforeLoad = 1;
        for (int k = 0; k < N - 1; k++) {
            if (map[i][k] == map[i][k + 1]) {
                beforeLoad++;
                continue;
            }

            if (map[i][k] > map[i][k + 1]) {
                int load = leftRight(map, i, k + 1);
                if (load == -1) {
                    flag = false;
                    break;
                }
                k = load - 1;
                beforeLoad = 0;
                continue;
            }

            if (map[i][k] < map[i][k + 1]) {
                if (beforeLoad < L) {
                    flag = false;
                    break;
                }
                beforeLoad = 1;
                continue;
            }
        }
        if (flag) resultCount++;
    }
}

 

[전체 코드]

 

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;


//경사가 오른쪽으로 내려가있다면 0 위로 1 왼쪽 2 아래는 3
int N, L;
int resultCount = 0;

vector<vector<int>> arr;
vector<vector<int>> arr2;


void Input() {
	cin >> N >> L;
	arr.resize(N);

	for (int i = 0; i < N; i++) {
		arr[i].resize(N);
	}
	arr2 = arr;

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> arr[i][k];
			arr2[k][i] = arr[i][k];
		}
	}
}

bool isDifTwo(vector<vector<int>>& map, int sero) {
	for (int i = 0; i < N - 1; i++) {
		int dif = map[sero][i] - map[sero][i + 1];
		if (abs(dif) >= 2)return true;
	}
	return false;
}
bool isAllSame(vector<vector<int>> &map,int sero) {
	for (int i = 0; i < N - 1; i++) {
		if (map[sero][i] != map[sero][i + 1])return false;
	}
	resultCount++;
	return true;
}
int leftRight(vector<vector<int>>& map, int sero, int garo) {
	
	int beforeLoad = 1;
	
	if (beforeLoad == L) {
		return garo;
	}
	if (garo == N - 1)return -1;
	for (int i = garo; i < N-1; i++) {
		
		

		if (map[sero][i] == map[sero][i + 1]) {
			beforeLoad++;
		}
		else {
			return -1;
		}
		if (beforeLoad == L) {
			return i+1;
		}
		

		
	}
	return -1;
	
}

void makeGame(vector<vector<int>>& map) {
	
	for (int i = 0; i < N; i++) {
		if (isAllSame(map, i) == true)continue;
		if (isDifTwo(map, i) == true) continue;
		
		bool flag = true;
		int beforeLoad = 1;
		for (int k = 0; k < N-1; k++) {
			if (map[i][k] == map[i][k + 1]) {
				beforeLoad++;
				continue;
			}

			 if (map[i][k] > map[i][k + 1]) {
				
				int load = leftRight(map, i, k+1);
				
				if (load == -1) {
					flag = false;
					break;
				}

				k = load-1;
				beforeLoad = 0;
				continue;
				
			}

			 if (map[i][k] < map[i][k + 1]) {
				if (beforeLoad < L) {
					flag = false;
					break;
				}
				beforeLoad = 1;
				continue;
			}
			
		}

		if (flag == true) resultCount++;
	}
}

void Print(vector<vector<int>>& map) {
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cout << map[i][k] << " ";
		}
		cout << "\n";
	}
}

int main(void) {
	Input();
	makeGame(arr);
	makeGame(arr2);

	cout << resultCount;
}