[백준/C++] 10844번. 쉬운 계단 수

문제

10844번: 쉬운 계단 수

---

1. 마지막 풀이

사고 과정

어려운 문제를 풀려면, 쉬운 문제부터 풀어봐야 한다.

 

비트마스킹과 DP를 이용한다고 알려진 계단 수 문제를 풀기 전에, 쉬운 계단 수가 있길래 풀어봤다.

 

문제는 간단하다. 인접한 자리끼리 1씩만 차이나는 수를 계단 수라고 할 때, n자리 계단 수는 총 몇 개인가?

 

이친수 문제와 비슷하게, 끝자리 마다 숫자 개수를 저장해놓고 더하는 방식을 사용했다.

 

1. 2차원 배열 grid 선언, 크기는 [n + 1][10]
2. grid[1]을 초기화. 0은 0, 나머진 1.
3. 이후 배열들은 앞의 값을 이용해 계산. 예를 들어 grid[3][4]는 grid[2][3] + grid[2][5]
4. grid[n]의 값들을 모두 더해 출력

 

코드

#include <iostream>
#include <vector>

#define MAX 1000000000

int main() {
	int n;
	std::cin >> n;

	std::vector<std::vector<int>> grid(n + 1, std::vector<int>(10));
	grid[1][0] = 0;

	for (int i = 1; i < 10; i++) {
		grid[1][i] = 1;
	}

	for (int i = 2; i <= n; i++) {
		grid[i][0] = grid[i - 1][1] % MAX;
		grid[i][1] = (grid[i - 1][0] + grid[i - 1][2]) % MAX;
		grid[i][2] = (grid[i - 1][1] + grid[i - 1][3]) % MAX;
		grid[i][3] = (grid[i - 1][2] + grid[i - 1][4]) % MAX;
		grid[i][4] = (grid[i - 1][3] + grid[i - 1][5]) % MAX;
		grid[i][5] = (grid[i - 1][4] + grid[i - 1][6]) % MAX;
		grid[i][6] = (grid[i - 1][5] + grid[i - 1][7]) % MAX;
		grid[i][7] = (grid[i - 1][6] + grid[i - 1][8]) % MAX;
		grid[i][8] = (grid[i - 1][7] + grid[i - 1][9]) % MAX;
		grid[i][9] = grid[i - 1][8] % MAX;
	}

	int answer = 0;
	for (int i = 0; i < 10; i++) {
		answer += grid[n][i];
		answer %= MAX;
	}

	std::cout << answer;
}

 

문제 자체는 어렵지 않다. 다만 노가다일 뿐.

값이 long long으로도 모자랄 만큼 올라가기에, 각 단계마다 MAX(1,000,000,000)로 나눠가며 계산했다. 모듈러 연산 역시 분배 법칙이 적용된다.

 

결과

다행히 결과는 성공. 하지만 이제부터 시작이다.

---

개선

사고 과정

먼저, 이친수처럼 규칙이 있는지 찾아봤다. 하지만 항이 워낙 많기도 했고, 규칙은 찾을 수 없었다.

 

그래서 그냥 로직은 유지하되, 최적화만 하기로 했다.

 

먼저, grid[i]를 0부터 10까지 한 것 대신, 반복문을 써보자.

 

for (int i = 2; i <= n; i++) {
	grid[i][0] = grid[i - 1][1] % MAX;
	for (int j = 1; j < 9; j++) {
		grid[i][j] = grid[i - 1][j - 1] + grid[i - 1][j + 1] % MAX;
	}
	grid[i][9] = grid[i - 1][8] % MAX;
}

 

그럼 우선 이렇게 줄일 수 있다. 여기서 0, 9의 경우도 통합하려면, 배열의 양끝에 더미를 추가하면 된다.

for (int i = 2; i <= n; i++) {
	for (int j = 0; j <= 9; j++) {
		grid[i][j] = grid[i - 1][j - 1] + grid[i - 1][j + 1] % MAX;
	}
}

 

초기 값을 0으로 초기화하면, 이처럼 더미를 이용해 양 끝 예외를 통합할 수 있다. 다만, 0이 유효한 값이었던 만큼 -1 인덱스를 사용하게 된다. 그러니 한 칸씩 미뤄, grid[i][2]는 1을 나타내게끔 표현한다. 해석은 어려워지지만, 내부적으론 효율적이다.

만약 이 방식이 싫다면 위처럼 0, 9만 따로 계산하자.

for (int i = 2; i <= 10; i++) {
	grid[1][i] = 1;
}

for (int i = 2; i <= n; i++) {
	for (int j = 1; j <= 10; j++) {
		grid[i][j] = (grid[i - 1][j - 1] + grid[i - 1][j + 1]) % MAX;
	}
}

int answer = 0;
for (int i = 1; i <= 10; i++) {
	answer += grid[n][i];
	answer %= MAX;
}
std::cout << answer;

 

그럼 범위가 위처럼 모두 바뀐다.

 

다른 개선 여부도 있다. 이 문제 같은 경우, dp[i]가 dp[i - 2]를 참조하는 등, 과거 기록을 사용하는 연산이 없다. 이 문제는 오직 직전 값 하나만 있으면, n까지 값을 구하는데 지장이 없다.

 

그러니 배열의 크기도 [2][10]으로 고정하고, 0과 1을 반전시켜가며 답을 구할 수 있다.

 

직전 배열만 저장하는 건 내가 떠올린 부분이지만, 이를 0과 1의 반전으로 구현하는 방법은 다른 분의 코드를 보고 알았다.

https://www.acmicpc.net/source/4408282

 

여기까지 완료하면, 코드는 이렇게 바뀐다.

 

for (int i = 2; i <= 10; i++) {
	grid[1][i] = 1;
}

for (int i = 2; i <= n; i++) {
	for (int j = 1; j <= 10; j++) {
		grid[i][j] = (grid[i - 1][j - 1] + grid[i - 1][j + 1]) % MAX;
	}
}

int answer = 0;
for (int i = 1; i <= 10; i++) {
	answer += grid[n][i];
	answer %= MAX;
}
std::cout << answer;

 

초기 값 설정 범위도, 끝에 답을 모두 더하는 부분도 수정이 이뤄졌다.

 

코드

#include <iostream>
#include <vector>

#define MAX 1000000000

int main() {
	int n;
	std::cin >> n;

	int grid[2][12] = { 0 };

	for (int i = 2; i <= 10; i++) {
		grid[0][i] = 1;
	}

	int k = 0;
	for (int i = 2; i <= n; i++) {
		k = (k == 0);
		for (int j = 1; j <= 10; j++) {
			grid[k][j] = (grid[!k][j - 1] + grid[!k][j + 1]) % MAX;
		}
	}

	int answer = 0;
	for (int i = 1; i <= 10; i++) {
		answer += grid[k][i];
		answer %= MAX;
	}
	std::cout << answer;
}

이전에 비해 코드가 훨씬 간결해졌다. 가독성은 조금 낮아졌지만.

결과

역시나 문제 없다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/4586941

behind06님의 깔끔한 코드. 배울 점도 많다.

 

내 코드와 비교

1. 나는 1,000,000,000을 define을 사용해 저장했고, 이 분은 그냥 변수 m으로 저장했다. 이처럼 const 변수를 쓰는 쪽이 더 권장된다.
2. 나는 k를 !를 통해 반전시켰지만, 이 분은 [(i+2)%2]라는 방법으로 두 배열을 스위칭했다. 이러면 변수값을 직접 스위칭하지 않아도, 그저 ++만으로 다룰 수 있게 된다.
3. 출력에 lld(long long)을 사용하셨다. 다만, 답은 항상 10억 이하기 때문에 이 경우엔 int를 써도 무방하다.

꽤나 배울 점이 많은 코드였다.

---

강평

계단 수 문제를 풀기 전, 가볍게 풀었던 쉬운 계단 수. 로직은 간단하나 코드를 최적화하는 방법이 다양했다.

 

0과 1 스위칭을 !로 할 수도, ( == 0)으로 할 수도, %2로 할 수도 있다는 걸 배웠고, 이는 상황 별로 다르게 쓸 수 있을 듯하다. 더 나아가면 & 0도 가능할 것이다.

 

여러모로 난이도는 쉽지만 배울 점이 많아 좋았던 문제다.