• Home
  • About
    • 코드좀비 photo

      코드좀비

      An amazing website.

    • Learn More
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[BOJ] 백준 14890 경사로 간단한설명과 코드 C++

14 Jan 2020

Reading time ~2 minutes

문제 정보

백준 ( BOJ ) 14890 경사로

문제 풀이 : 시뮬레이션

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

시작 Thinking

a`

.. 첨에 경사로 한번 놓은곳에는 (가로 혹은 세로 ) 못놓는줄 알고 삽질을 많이 헀다.

그러나 그렇게 어려운 문제가 아니였던걸로…

문제 풀이

시뮬레이션으로 진행 해 주면 된다.

가로 세로 탐색을 따로 코딩 하면 코딩 길이가 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로 어떻게 짤지 고민하다가

도저히 안풀려 암울하다가 …

문제가 좀더 상세했으면 좋았을뻔..



백준C++시뮬레이션 Share Tweet +1