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

1.문제설명

갈 수 있는 길인지 판단하고(한 줄의 모든 숫자가 같은 지),

경사로를 둬서 갈 수 있는 길로 만들 수 있는지 확인해야한다.

2.접근방법[알고리즘]

먼저 모든 숫자가 같은지 확인하고,

모든 숫자가 같지 않다면

경사로를 둬서 갈 수 있는 길인지 확인하기 위해서

각 행을 해당 숫자와 해당 숫자의 개수로 표현했다.

6 2
3 3 3 3 3 3
2 3 3 3 3 3
2 2 2 3 2 3
1 1 1 2 2 2
1 1 1 3 3 1
1 1 2 3 3 2

이런 입력의 경우 가로 행만 살펴보면

6 2                 Num : Count
3 3 3 3 3 3        -> 3 : 6
2 3 3 3 3 3           2 : 1 , 3 : 5
2 2 2 3 2 3           2 : 3, 3 : 1 , 2 : 1 , 3 : 1
1 1 1 2 2 2           1 : 3, 2 : 3
1 1 1 3 3 1           1 : 3 , 3 : 2 , 1 : 1 
1 1 2 3 3 2           1 : 2, 2 : 1 , 3 : 2 , 2 : 1

이렇게 표현 할 수 있다

이렇게 한 줄에 대한 정보를 표현하고

L 변수를 이용해서 경사로를 둘 수 있는 지 없는 지 판단 할 수 있다

L = 2 일 때

3 : 6 은 모두 같은 숫자이므로 길이다.

2 : 1 , 3 : 5

이 줄에는 경사로를 둬서 길을 만들 수 없다.

숫자가 작은 부분의 길이가 L보다 작기 때문이다.

2 : 3 , 3 : 1, 2 :1 , 3: 1

이 줄도 2:1 이므로 2의 길이가 L보다 작으므로 길이 될 수 없다

1 : 3 , 2 : 3

1의 길이가 3이므로 L보다 커서 길이 될 수 있다.

예외

L이 동일하게 2일 때

3 3 2 2 3 3

이런 경우는 2에 경사로를 한 번 두면 더이상 경사로를 또 둘 수 없기 때문에 길이 될 수 없다.

이러한 경우들을 코드로 구현해보면

void Count(int arr[101][101]) {
	for (int i = 1; i <= n; i++) {
		int val = 0, cnt = 0;
		
        //v 벡터에 한 줄 정보 표현 
		vector<pair<int, int> > v;
		for (int j = 1; j <= n; j++) {
			if (j == 1) {
				val = arr[i][j];
				cnt = 1;
				continue;
			}

			if (arr[i][j] == val) {
				cnt++;
			}
			else {
				v.push_back({ val,cnt });
				val = arr[i][j];
				cnt = 1;
			}
		}
		v.push_back({ val,cnt });
		
        // 모두 같은 숫자인 경우 
		if (v.size() == 1) {
			ans++;
			continue;
		}

		//경사로 추가해서 길을 만들 수 있는지 확인 
		bool canmake = true;

		for (int k = 0; k < v.size() - 1; k++) {
        	// 높이 차이가 1보다 크면 길이 될 수 없다.
			if (abs(v[k].first - v[k + 1].first) > 1) {
				canmake = false;
				break;
			}


			if (v[k].first < v[k + 1].first) {
				if (v[k].second < l) {
					canmake = false;
					break;
				}
			}
			else {
				if (v[k + 1].second < l) {
					canmake = false;
					break;
				}
				else {
                	// 332233 같은 경우를 위해 경사로를 두면 count에서 빼준다.
					v[k + 1].second -= l;
				}

			}
		}
		if (canmake) ans++;
	}

}

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, l, arr[101][101], arr2[101][101], ans;

void Count(int arr[101][101]) {
	for (int i = 1; i <= n; i++) {
		int val = 0, cnt = 0;

		vector<pair<int, int> > v;
		for (int j = 1; j <= n; j++) {
			if (j == 1) {
				val = arr[i][j];
				cnt = 1;
				continue;
			}

			if (arr[i][j] == val) {
				cnt++;
			}
			else {
				v.push_back({ val,cnt });
				val = arr[i][j];
				cnt = 1;
			}
		}
		v.push_back({ val,cnt });

		if (v.size() == 1) {
			ans++;
			continue;
		}

		//경사로 추가해서 길을 만들 수 있는지 확인 
		bool canmake = true;

		for (int k = 0; k < v.size() - 1; k++) {
			if (abs(v[k].first - v[k + 1].first) > 1) {
				canmake = false;
				break;
			}

			if (v[k].first < v[k + 1].first) {
				if (v[k].second < l) {
					canmake = false;
					break;
				}
			}
			else {
				if (v[k + 1].second < l) {
					canmake = false;
					break;
				}
				else {
					v[k + 1].second -= l;
				}

			}
		}
		if (canmake) ans++;
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> l;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			arr2[j][i] = arr[i][j];
		}
	}
	
	Count(arr);
	Count(arr2);


	cout << ans << '\n';


	return 0;

}

이 문제에서 가로방향 길과 세로방향 길의 개수를 모두 세야한다.

하지만 가로방향이나 세로방향이나 길을 세는 방법이 동일하기 때문에

arr2 배열을 arr과 대칭적으로 입력해주어 동일하게 Count 하면

쉽게 답을 구할 수 있다.