문제 정보
백준 ( BOJ ) 14890 경사로
문제 풀이 : 시뮬레이션
문제 출처 : https://www.acmicpc.net/problem/14890
시작 Thinking
.. 첨에 경사로 한번 놓은곳에는 (가로 혹은 세로 ) 못놓는줄 알고 삽질을 많이 헀다.
그러나 그렇게 어려운 문제가 아니였던걸로…
문제 풀이
시뮬레이션으로 진행 해 주면 된다.
가로 세로 탐색을 따로 코딩 하면 코딩 길이가 2배가 되는데,
그렇게 하지 말고 익숙한 가로 한방향만 탐색을 하고,
가로 세로를 뒤집어서 진행하면 코드 길이를 줄일 수 있다.
높이를 계속 체크해가며, 높이가 다를시 +1, -1 인경우 체크 해보면 되는데,
+1인 경우 뒤로 되돌아 가서 탐색을 해야 한다.
(꼭 뒤로 되돌아 가서 탐색을 할 피요는 없긴 하다.
매번 같을때마다 카운트를 더해가며, 높이가 달라지면 카운트를 리셋하는 방식을 사용하면,
뒤로 되돌아 갈 필요가 없게 된다. )
-1인 경우 앞으로 가면서 체크 해주면 된다.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, l;
int fun(vector<vector<int>> & map) {
int temp;
int error = 1;
int xresult = 0;
for (int i = 0; i < n; i++) {
temp = map[i][0];
error = 0;
for (int j = 1; j < n; j++) {
if (temp == map[i][j])
continue;
// 내려가는 방향
else if (temp == map[i][j] + 1) {
temp--;
for (int k = j; k < j + l; k++) {
if (k >= n) {
error = 1;
break;
}
if (temp != map[i][k]) {
error = 1;
break;
}
map[i][k] = -1;
}
if (error)
break;
else
j += l-1;
}
// 올라가는 방향
else if (temp == map[i][j] - 1) {
temp++;
for (int k = j - 1; k > j - l - 1; k--) {
if (k < 0) {
error = 1;
break;
}
if (temp != map[i][k] + 1) {
error = 1;
break;
}
map[i][k] = -1;
}
if (error)
break;
}
else {
error = 1;
break;
}
}
if (error == 0) {
xresult++;
}
}
return xresult;
}
int main() {
int temp;
cin >> n >> l;
vector<vector<int>> map(n, vector<int>(n, 0));
vector<vector<int>> xmap(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> temp;
map[i][j] = temp;
xmap[j][i] = temp;
}
}
cout << fun(map) + fun(xmap);
return 0;
}
문제 후기
소요 시간 : 96 분
틀린 횟수 : 0 번
발생 에러 : 없음
예제에 대해 분석을 잘 해보자.. 괜히 dfs로 어떻게 짤지 고민하다가
도저히 안풀려 암울하다가 …
문제가 좀더 상세했으면 좋았을뻔..