BOJ 14890 경사로

문제출처 : https://www.acmicpc.net/problem/14890

1. 문제요약

2. 접근방법

3. 시간복잡도

4. 회고

소스코드 : 내방식

#include<iostream>
using namespace std;

int n, l, map[2][101][101], check[2][101][101], ans = 0;

int main(void){
	cin >> n >> l;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			cin >> map[0][i][j];
			map[1][j][i] = map[0][i][j];
		}
	}
	
	for (int i = 0; i < 2; i++){
		for (int j = 0; j < n; j++){
			int k = 0;
			for (; k < n - 1; k++){
				if (map[i][j][k] == map[i][j][k + 1]) continue;
				else if (map[i][j][k] + 1 == map[i][j][k + 1]){
					if (k + 1 - l >= 0){
						int m = k + 1 - l;
						if (m == k)
							if (check[i][j][m])
								break;
						for (; m < k; m++){
							if (map[i][j][m] != map[i][j][m + 1] || check[i][j][m] || check[i][j][m + 1]){
								break;
							}
						}
						if (m == k){
							for (int a = k + 1 - l; a < k + 1; a++){
								check[i][j][a] = true;
							}
							continue;
						}
						else break;
					}
					else break;
				}
				else if (map[i][j][k] - 1 == map[i][j][k + 1]){
					if (k + l < n){
						int m = k + 1;
						if (m == k + l)
							if (check[i][j][m])
								break;
						for (; m < k + l; m++){
							if (map[i][j][m] != map[i][j][m + 1] || check[i][j][m] || check[i][j][m + 1]){
								break;
							}
						}
						if (m == k + l){
							for (int a = k + 1; a < k + l + 1; a++){
								check[i][j][a] = true;
							}
							continue;
						}
						else break;
					}
					else break;
				}
				else break;
			}
			
			if (k == n - 1)
				ans++;
		}
	}
	cout << ans << "\n";
}

소스코드 : 내가 부족했던 1을 보완한 방식

#include<stdio.h>

int main(void){
	int input[100][100], i, j, n, l, arr[200][100], mark[100] = { 0 }, k, ans = 0, flag;
	scanf("%d %d", &n, &l);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			scanf("%d", &input[i][j]);
			arr[i][j] = input[i][j];
		}
	}

	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			arr[i + n][j] = input[j][i];
		}
	}

	for (int i = 0; i < 2 * n; i++){
		flag = 1;
		for (int j = 0; j < n; j++)
			mark[j] = 0;

		for (int j = 0; j < n - 1 && flag; j++){
			if (arr[i][j] == arr[i][j + 1] + 1){ //left higher
				for (int k = 1; k <= l; k++){
					if (mark[j + k] == 1 || j + l >= n || arr[i][j + k] != arr[i][j + 1]){
						flag = 0;
						break;
					}
					mark[j + k] = 1;
				}
			}
			else if (arr[i][j] + 1 == arr[i][j + 1]){
				for (int k = 0; k < l; k++){
					if (mark[j - k] == 1 || j - l < -1 || arr[i][j - k] != arr[i][j]){
						flag = 0;
						break;
					}
					mark[j - k] = 1;
				}
			}
			else if (arr[i][j] == arr[i][j + 1])
				continue;
			else{
				flag = 0;
				break;
			}
		}
		if (flag == 1)
			ans++;
	}
	printf("%d\n", ans);
}

소스코드 : 생각지도 못한 방식.. 부럽

#include <stdio.h>
 
int n, l, a[101][101], dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 }, ans;
 
int main() {
    scanf("%d%d", &n, &l);
    int i, j;
    for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf("%d", &a[i][j]);
    for (i = 0; i < n; i++) {
        int cnt = 1;
        for (j = 0; j < n - 1; j++) {
            if (a[i][j] == a[i][j + 1]) cnt++;
            else if (a[i][j] + 1 == a[i][j + 1] && cnt >= l) cnt = 1;
            else if (a[i][j] - 1 == a[i][j + 1] && cnt >= 0) cnt = -l + 1;
            else break;
        }
        if (j == n - 1 && cnt >= 0) ans++;
        cnt = 1;
        for (j = 0; j < n - 1; j++) {
            if (a[j][i] == a[j + 1][i]) cnt++;
            else if (a[j][i] + 1 == a[j + 1][i] && cnt >= l) cnt = 1;
            else if (a[j][i] - 1 == a[j + 1][i] && cnt >= 0) cnt = -l + 1;
            else break;
        }
        if (j == n - 1 && cnt >= 0) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]