글 읽기 - [C++] 1562 계단 수 접근 방법이 맞는지..

rndrnjs2003 5년 전 0

N = 10 일때 9876543210 이므로

N이 11부터는 앞 또는 뒤에 수가 추가되는 경우의 수 밖에 없을 것으로 판단되어 코드를 짰습니다.

앞(front)은 0이 올 수 없으므로 0, 1, 9일 때만 조건문을 걸어주었고

뒤(back)는 0 1일때만 조건문을 걸어주었습니다.

이렇게 접근하는 방법이 잘못되었을까요?ㅠㅠ

#include <iostream>
using namespace std;
long long memo[101];
long long front[101][10];
long long back[101][10];
int max(long long a, long long b) {
	return a > b ? a : b;
}
int main() {
	int N;
	cin >> N;
	long long f=0, b=0;
	memo[10] = 1;
	front[10][9] = 1;
	back[10][0] = 1;
	for (int i = 11; i <= N; i++) {
		for (int j = 0; j < 10; j++) {
			front[i][j] += front[i - 1][j];
			if (j == 0) {
				front[i][j + 1] += front[i - 1][j];
			}
			else if (j == 1) {
				front[i][j + 1] += front[i - 1][j];
			}
			else if (j == 9) {
				front[i][j - 1] += front[i - 1][j];
			}
			else {
				front[i][j + 1] += front[i - 1][j];
				front[i][j - 1] += front[i - 1][j];
			}
		}

		for (int j = 0; j < 10; j++) {
			back[i][j] += back[i - 1][j];
			if (j == 0) {
				back[i][j + 1] += back[i - 1][j];
			}
			else if (j == 9) {
				back[i][j - 1] += back[i - 1][j];
			}
			else {
				back[i][j + 1] += back[i - 1][j];
				back[i][j - 1] += back[i - 1][j];
			}
		}
		for (int j = 0; j < 10; j++) {
			f += front[i][j];
			f %= 1000000000;
			b += front[i][j];
			b %= 1000000000;
		}
		memo[i] = max(f, b);
	}
	cout << memo[N] << '\n';
}

portableangel 5년 전 1

987656787654343210 같은 수도 계단 수입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] 1562 계단 수 접근 방법이 맞는지..

rndrnjs2003 5년 전 0

portableangel 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말