글 읽기 - 이렇게 풀면 문제 의도대로 안 푼 건가요?

ajh1973456 2년 전 0

입력을 받기 위해 char[100000][3] 배열을 선언하고

dp를 하기 위한 int[100000][3] 배열을 선언하고 문제를 풀었는데,

3.5MB로 메모리 제한 밑으로 통과했습니다.

문제에서 메모리 제한을 4MB로 매우 낮게 준 게 문제 출제자가 원하는 풀이법이 있는 거 같은데,

위와 같은 방법으로 풀면 출제자의 의도대로 안 푼 걸까요?

만약 그렇다면 어떤 방법으로 풀어야 정석인지 질문 드립니다.

#include <iostream>

using namespace std;

char map[100001][3];
int dp[100001][3];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < 3; i++) {
		dp[1][i] = map[1][i] - '0';
	}

	int left, right;
	for (int i = 2; i <= N; i++) {
		left = max(dp[i - 1][0], dp[i - 1][1]);
		right = max(dp[i - 1][1], dp[i - 1][2]);

		dp[i][0] = left + map[i][0] - '0';
		dp[i][1] = max(left, right) + map[i][1] - '0';
		dp[i][2] = right + map[i][2] - '0';
	}
	cout << max(max(dp[N][0], dp[N][1]), dp[N][2]) << " ";

	for (int i = 2; i <= N; i++) {
		left = min(dp[i - 1][0], dp[i - 1][1]);
		right = min(dp[i - 1][1], dp[i - 1][2]);

		dp[i][0] = left + map[i][0] - '0';
		dp[i][1] = min(left, right) + map[i][1] - '0';
		dp[i][2] = right + map[i][2] - '0';
	}
	cout << min(min(dp[N][0], dp[N][1]), dp[N][2]);
}

0000000000 2년 전 1

원래 슬라이딩 윈도우 기법을 사용해서 푸는 것을 의도한 문제인 것 같으나 [100000][3]으로도 뚫리긴 합니다.

ajh1973456 2년 전 0

감사합니다. 덕분에 슬라이딩 윈도우 알아갑니다.

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

문제

문제

출처

ICPC

이렇게 풀면 문제 의도대로 안 푼 건가요?

ajh1973456 2년 전 0

0000000000 2년 전 1

ajh1973456 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말