[BOJ] 14890번 : 경사로

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n, L; 
int board[105][105]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> L; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) cin >> board[i][j];
	}
	int ans = 2 * n; 
	// 행부터 검사 
	for (int i = 0; i < n; i++) {
		int last_val = board[i][0]; 
		int cnt = 1;
		int j = 1;
		while (j < n) {
			if (last_val == board[i][j]) cnt++, j++;
			else if (last_val + 1 == board[i][j]) {
				if (cnt < L) {
					ans--;
					break;
				}
				last_val = board[i][j], cnt = 1, j++;
			}
			else if (last_val - 1 == board[i][j]) {
				if (j + L - 1 >= n) {
					ans--;
					break;
				}
				bool iswrong = false;
				for (int k = j; k < j + L; k++) {
					if (board[i][j] != board[i][k]) {
						ans--;
						iswrong = true;
						break;
					}
				}
				if (!iswrong) {
					last_val = board[i][j], cnt = 0;
					j += L;
				}
				else break;
			}
			else {
				ans--;
				break;
			}
		}
	}
	// 열 검사
	for (int i = 0; i < n; i++) {
		int last_val = board[0][i];
		int cnt = 1;
		int j = 1;
		while (j < n) {
			if (last_val == board[j][i]) cnt++, j++;
			else if (last_val + 1 == board[j][i]) {
				if (cnt < L) {
					ans--;
					break;
				}
				last_val = board[j][i], cnt = 1, j++;
			}
			else if (last_val - 1 == board[j][i]) {
				if (j + L - 1 >= n) {
					ans--;
					break;
				}
				bool iswrong = false;
				for (int k = j; k < j + L; k++) {
					if (board[j][i] != board[k][i]) {
						ans--;
						iswrong = true;
						break;
					}
				}
				if (!iswrong) {
					last_val = board[j][i], cnt = 0;
					j += L;
				}
				else break;
			}
			else {
				ans--;
				break;
			}
		}
	}
	cout << ans << '\n';
}

행과 열을 기준으로 for문을 두 번 돌렸다. 매우 비효율적이라는 것을 알았지만, 일단 푸는 것이 우선이라 끝까지 갔다. 

많은 시행착오 끝에 결국 풀었다. 나는 board라는 배열을 만들어, board에서 행과열을 보며, 답을 구했다.

 

3. solution 2 : 

// Authored by : jihwan0123
// Co-authored by : BaaaaaaaaaaarkingDog, dustmddus
// http://boj.kr/f7b9b1367b054a08a753f1096b829b26
#include <bits/stdc++.h>
using namespace std;

int n, l;
int board[102][102];

bool check(vector<int>& line){
  int idx = 0;
  int cnt = 1; // 현재 보고 있는, 높이가 같은 구간의 길이
  while (idx < n - 1) {
    // 높이 차이가 1보다 크면 설치 불가
    if (abs(line[idx + 1] - line[idx]) > 1) return 0;
    if (line[idx] == line[idx + 1]) { // 같으면 다음칸 체크
      cnt++;
      idx++;
    }
    else if (line[idx] < line[idx + 1]) { // 다음 칸이 더 높으면
      // l보다 작아서 경사로를 놓을 수 없으면 종료
      if (cnt < l) return 0;
      cnt = 1;
      idx++;
    }
    else {  // 다음 칸이 더 낮으면
      // l 길이 만큼 길이 없으면 경사로 설치 불가
      if (idx + l >= n) return 0;
      for (int i = idx + 1; i < idx + l; i++)
        if (line[i] != line[i + 1]) return 0;
      idx = idx + l; // 경사로 설치했으면, 설치한 칸부터 다음칸과 비교
      cnt = 0;
    }
  }
  return 1;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> l;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      cin >> board[i][j];
      
  int ans = 0;

  // 가로
  for (int i = 0; i < n; i++){
    vector<int> line;
    for(int j = 0; j < n; j++) line.push_back(board[i][j]);
    ans += check(line);
  }

  // 세로
  for (int i = 0; i < n; i++){
    vector<int> line;
    for(int j = 0; j < n; j++) line.push_back(board[j][i]);
    ans += check(line);
  }
  cout << ans;
}
/*
2N개의 길에 대해 각각 경사로 설치 여부 확인
*/

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/14890.cpp

basic-algo-lecture/0x0D/solutions/14890.cpp at master · encrypted-def/basic-algo-lecture

vector를 만들어 한 줄씩 검사하도록 하고 있다. 이렇게 하면, 내 코드에서 불필요하게 for문 두 번을 길게 쓸 필요가 없다. 계산 logic은 함수를 이용하여 깔끔하게 처리했다.