백준 1562, 계단 수

문제

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

풀이

처음에는 이 문제를 보고 왜 이걸 비트 마스킹을 사용해서 풀어야 할까... 생각을 했는데 나중에 문제를 보니까 모든 숫자를 사용한 계단수도 고려해야 하는 것을 보지 못했다... 다만 이렇게 계단수만 세는 코드를 먼저 구현하고 그 다음에 비트 마스킹을 사용하니 문제에 대한 이해가 된 상태에서 진행할 수 있어서 좋았다. 이번에 백준 책을 읽어서 문제풀이 알고리즘을 여기에 한번 적용해보면, 먼저 문제를 읽고 나만의 언어로 재정의 하는 부분에서 문제를 제대로 이해하지 못한게 실수중하나라고 생각하고 그 다음에 비트를 다루는 부분에서 처음에는 (기존 비트 마스킹) + (1 << i) & 1023 같은 식으로 사용하면 1023 이하의 것들 중에서 1인 것만 골라지지 않을까 생각을 했는데 다시 생각해보니 더해지면서 그 이상의 비트가 되는 경우가 있어서 아니였다. 그래서 비트가 이미 있는 경우에는 안더하고 없으면 더하는 식으로 변경하였다. 이외에도 자잘한 실수(+ - 위치 제대로 맞추기, 범위 등)도 있었는데 그건 위의 비트 실수를 고치기 전에 웬만하면 다 고쳐서 찾는데 그리 크게 오래 걸리지 않았다.

다음에는 문제를 더욱 더 잘 읽고 이해를 한 다음에 간단한 식으로 쉽게 생각해서 추상화하고 계획을 세우고 검증한 다음에 프로그래밍을 시작해야 하지 않을까라는 생각이 들었다.

또한 이번에는 문제가 쉬워서 반례나 디버깅을 사용하지 않고 풀었는데 이런 습관을 미리미리 길러서 대회용으로 문제풀이를 할 수 있도록 해야겠다. 이번 문제는 문제가 간단했는데도 오래 걸려서 좀더 수련을 해야된다고 생각한다.

걸린 시간 : 42분 40초

실수

• 문제를 잘못읽는 실수를 저질렀다. (모든 숫자를 사용해야 하는 것을 읽지 못함)
• 비트 마스킹 관련 연산을 잘못함(위에 적혀있는 대로)

코드

초기 버전

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> dp(10, vector<int>(100, 0)); // [마지막으로 끝나는 숫자][N]

int main() {
	int n;

	scanf("%d", &n);

	for (int i = 1; i < 10; i++) { // 0으로 시작하는 숫자는 고려하지 않음
		dp[i][1] = 1;
	}

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 10; j++) {

			if (j == 0) {
				dp[j][i] = dp[j + 1][i - 1] * 10;
			}

			else if (j == 9) {
				dp[j][i] = dp[j - 1][i - 1] * 10;
			}

			else {
				dp[j][i] = dp[j - 1][i - 1] * 10 + dp[j + 1][i - 1] * 10;
			}

			dp[j][i] %= 1000000000;

		}
	}

	int res = 0;

	for (int i = 0; i < n; i++) {
		res = (res + dp[i][n]) % 1000000000;
	}

	printf("%d", res);

	return 0;
}

제출 버전

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>

using namespace std;

vector<vector<vector<int>>> dp(101, vector<vector<int>>(10, vector<int>(1024, 0))); // [길이][마지막으로 끝나는 숫자][숫자 등장 여부(비트 마스킹)]

void print(int i) {
	for (int j = 0; j < 10; j++) {
		for (int k = 0; k < 1024; k++) {
			printf("%d ", dp[i][j][k]);
		}
		printf("\n");
	}
}

int main() {
	int n;

	scanf("%d", &n);

	for (int i = 1; i < 10; i++) { // 0으로 시작하는 숫자는 고려하지 않음
		dp[1][i][1 << i] = 1;
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			for (int k = 1; k < 1024; k++) {

				if (j == 0) {
					dp[i + 1][j + 1][(k & (1 << (j + 1))) == 0 ? (k + (1 << (j + 1))) : k] += dp[i][j][k];
					dp[i + 1][j + 1][(k & (1 << (j + 1))) == 0 ? (k + (1 << (j + 1))) : k] %= 1000000000;
				}
				else if (j == 9) {
					dp[i + 1][j - 1][(k & (1 << (j - 1))) == 0 ? (k + (1 << (j - 1))) : k] += dp[i][j][k];
					dp[i + 1][j - 1][(k & (1 << (j - 1))) == 0 ? (k + (1 << (j - 1))) : k] %= 1000000000;
				}
				else {
					dp[i + 1][j + 1][(k & (1 << (j + 1))) == 0 ? (k + (1 << (j + 1))) : k] += dp[i][j][k];
					dp[i + 1][j - 1][(k & (1 << (j - 1))) == 0 ? (k + (1 << (j - 1))) : k] += dp[i][j][k];
					dp[i + 1][j + 1][(k & (1 << (j + 1))) == 0 ? (k + (1 << (j + 1))) : k] %= 1000000000;
					dp[i + 1][j - 1][(k & (1 << (j - 1))) == 0 ? (k + (1 << (j - 1))) : k] %= 1000000000;
				}

			}
		}
	}

	int res = 0;

	for (int j = 0; j < 10; j++) {
		res = (res + dp[n][j][1023]) % 1000000000;
	}

	printf("%d", res);

	return 0;
}