글 읽기 - 틀렸습니다ㅠㅠ래요 도와주세요

chjiiwon30 5년 전 0

안녕하세요 질문 첨 올려봅니당

이 문제는 백트래킹, bfs로 푸는 거라던데, 저는 이 사실을 알지 못하고 dp로 풀었더랬죠...

물론 폭풍 검색해서 게시판에 이미 있는 반례랑 예외처리 다해줬고 답 잘 나옵니다(맞왜틀ㅈㅅㅠㅠ)

bfs로 풀어도되지만 dp로 푼 이 코드가 도대체 어디가 어떻게 틀린것인지 매우매우 궁금해서 이렇게 질문을 올려봅니다...

아니면 제가 놓친 반례, 예외, 문제들이 있어서 dp로는 풀 수 없는 것인지 궁금합니다ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;

int n, k;
int d[100001];

int main() {
	scanf("%d %d", &n, &k);

    //동생<수빈 일경우 갈수있는 방법이 무조건 '현재-1'일거라 생각
	if (n > k) { 
		printf("%d\n", n - k);
		return 0;
	}
	
	d[n] = 0;    //시작은 0초
    //초기화 부분
	if (n == 0)
		d[n + 1] = 1;    //음수는 생각하지 않음
	else
		d[n - 1] = d[n + 1] = 1;

    //n k가 5 17이라 하면 (i:7~18)
	for (int i = n + 2; i <= k + 1; i++) {
        //i가 짝수일경우 min(x+1걷기, 순간이동)
		if (i % 2 == 0)
			d[i] = min(d[i - 1] + 1, d[i / 2] + 1);
		else    //홀수일경우 x+1걷기
			d[i] = d[i - 1] + 1;

        //d[i]를 채운이후 d[i-1]의 값 갱신->x-1걷기가 최소인지 확인해서 갱신
		d[i - 1] = min(d[i - 1], d[i] + 1);
	}

	printf("%d\n", d[k]);

	return 0;
}

zxcvber 5년 전 1

우선 반례를 몇 가지 말씀 드리자면 다음이 있습니다

6 8

Got: 1

Expected: 2

6 9

Got: 2

Expected: 3

6 16

Got: 2

Expected: 3

zxcvber 5년 전 1

추가적으로 발견한 부분이 있어 글을 남깁니다

DP를 하는 과정에서 DP table 을 n - 1 부터 채우면 그 이하의 값들을 참조할 때 문제가 생깁니다

n - 1 이하의 숫자들에 대해서 DP table 값을 채워주니 잘 통과가 되네요!

아래는 통과한 소스와 수정한 부분입니다

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;

int n, k, d[100001];

int main() {
	scanf("%d %d", &n, &k);
	if (n > k) {
		printf("%d\n", n - k);
		return 0;
	}
	d[n] = 0;
	if (n == 0)
		d[n + 1] = 1;
	else
		d[n - 1] = d[n + 1] = 1;

    // Modified
    int idx = n - 2, tmp = 2;
    while(idx >= 0) {
        d[idx] = tmp;
        idx--;
        tmp++;
    }
    // End

	for (int i = n + 2; i <= k + 1; i++) {
		if (i % 2 == 0) d[i] = min(d[i - 1] + 1, d[i / 2] + 1);
		else d[i] = d[i - 1] + 1;
		d[i - 1] = min(d[i - 1], d[i] + 1);
	}
    printf("%d", d[k]);
	return 0;
}

chjiiwon30 5년 전 1

zxcvber님 정말 감사합니다ㅠㅠ 속시원히 해결되서 너무 기분좋아요ㅠㅠㅠㅠㅜ공부열심히할게요흑흑

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

문제

문제

출처

ICPC

틀렸습니다ㅠㅠ래요 도와주세요

chjiiwon30 5년 전 0

zxcvber 5년 전 1

zxcvber 5년 전 1

chjiiwon30 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말