[C++] 백준(BOJ) - 14890 : 경사로

17 Nov 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 14890 : 경사로(링크)

알고리즘

1. 브루트포스

풀이

1. 행열 체크 / 열행 체크
   • 대칭 배열을 활용하여 열행 체크를 할 수 있다
2. 얼핏 보면 cnt 변수를 두개 활용해야 할 것 같지만 내리막에서는 cnt를 음수로 만들어서 처리할 수 있다
   • 오르막의 경우 cnt >= l 인 경우 cnt = 1로 초기화
   • 내리막의 경우 cnt >= 0 인 경우 cnt = -l + 1로 초기화
   • 평지의 경우 cnt++
3. 모든 열을 돌았을 때, cnt >= 0 인지 확인

코드

// BOJ-14890 : 경사로
#include<bits/stdc++.h>
using namespace std;

int n, l, res = 0, a[104][104], b[104][104];

void solve(int v[104][104])
{
	for (int i = 0; i < n; i++)
	{
		int cnt = 1;
		int j;
		for (j = 0; j < n - 1; j++)
		{
			if (v[i][j] == v[i][j + 1]) cnt++; // 평지일 때 (카운트를 센다)
			else if (v[i][j] + 1 == v[i][j + 1] && cnt >= l) cnt = 1; // 오르막을 만났을 때
			else if (v[i][j] - 1 == v[i][j + 1] && cnt >= 0) cnt = -l + 1; // 내리막을 만났을 때
			else break;
		}
		if (j == n - 1 && cnt >= 0) res++;
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> l;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
			b[j][i] = a[i][j];
		}
	}

	solve(a); 
	solve(b);

	cout << res << '\n';
	return 0;
}

평가

• 행열의 단순 체크의 경우 대칭 행렬을 만들어서 하나의 함수로 재사용 가능
• cnt 변수를 사용할 때, 하나의 변수로 사용할 수는 없을까 고려해서 코드 압축을 할 수 있도록 한다