글 읽기 - 틀린 테스트케이스를 못찾겠습니다ㅠ.ㅠ

ll1000wooll 7년 전 0

캐쉬배열을 제일 첫단어 인덱스, 빈칸의 갯수 형식으로 메모이제이션해서

빽트랙킹 돌렸습니다..

TC 만들어서 캐쉬 제대로 태우는지 다 일일이 확인해봤는데도 도무지 틀린답을 못찾겠습니다 ㅠ.ㅠ

도와주십시용ㅠㅠㅠㅠㅠ

#include <stdio.h>
#include <iostream>
#define INF 987654321
using namespace std;
int n, m;
int ans;
int arr[1002];
int check[1002][1002];
int bck(int step, int tnt) {
	if (step + tnt == n) {
		check[step][tnt] = 0;
		return 0;
	}
	if (check[step][tnt] != -1) {
		return check[step][tnt];
	}
	if (step >= n) {
		check[step][tnt] = 0;
		return 0;
	}
	int result = INF;
	int cnt = 0;
	int total = 0;
	int start_point = step + tnt + 1;
	for (int i = start_point; i <= n; i++) {
		total = total + arr[i] + cnt; //이름 수
		if (total <= m) {
			int tmp = bck(start_point, cnt);
			if (result > tmp) {
				result = tmp;
			}
			cnt++;
		}else{
			break;
		}
	}
	if (step == 0 && tnt == 0) {
		return result;
	}
	int here = 0;
	int here_cnt = -1;
	for (int i = step; i < start_point; i++) {
		here = here + arr[i];
		here_cnt++;
	}
	here = here + here_cnt;
	int pow_here = (m - here)*(m - here);
	int return_here = result + pow_here;
	check[step][tnt] = return_here;
	return return_here;
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
	}
	for (int i = 0; i < 1002; i++) {
		for (int j = 0; j < 1002; j++) {
			check[i][j] = -1;
		}
	}
	cout << bck(0, 0) << "\n";
	return 0;
}

zlzmsrhak 7년 전 1

먼저 반례는

3 7

답: 0

1. 제가 코드를 보기에는 캐시 배열이 check[첫 단어 인덱스][끝 단어 인덱스] 인 것 처럼 보입니다.

10번째 줄의 종료 조건이 (두 값의 합이 n과 같다)인 것이나, 24번째 줄 start_point가 (두 값의 합) + 1 인 것을 보면요..

제가 보기엔 적어도 빈 칸의 갯수는 아닌 것 같습니다.

2. 26번째 줄에서 cnt 값이 늘어나는데도 불구하고 total에 cnt 값을 계속 누적시켜서 잘못된 값을 가지고 있을 거 같은 느낌이 듭니다.

3. 지금 코드 시간복잡도는 O(N^3)이기 때문에 최적화를 해야 될 것 같습니다.

4. 메모이제이션은 백트래킹이라고 안합니다.

ll1000wooll 7년 전 0

상세한 답변 감사드립니다.

처음 알고리즘을 짤때 cnt는 빈칸이 들어가는 갯수로 생각하고 구현을 하였습니다ㅠㅠ

첫단어 인덱스 + cnt 의 경우 첫 인덱스에서 빈칸 갯수를 더해줌으로 끝인덱스라고 볼수도 있겠군요!

2번에서 말씀해주신 문제점을 디버깅 해보니 cnt 값이 계속 누적된 문제점이 맞았습니다.

나머지 지적해주신 부분도 숙지하도록 하겠습니다 감사합니다^^

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

문제

문제

출처

ICPC

틀린 테스트케이스를 못찾겠습니다ㅠ.ㅠ

ll1000wooll 7년 전 0

zlzmsrhak 7년 전 1

ll1000wooll 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말