글 읽기 - 1514 자물쇠 질문 드립니다.

hbh1107 7년 전 0

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

안녕하세요. 자물쇠 문제 지금 두달 째 못풀고 있습니다. ㅜ

그래서 조언 구하고자 글 올립니다. 어떤 부분이 고려되지 않았는지 알려주시면 감사하겠습니다.

1. 풀이 방식 : dp[cur][n1][n2] : 현재 처리해야 될 디스크 위치가 cur이고 cur위치의 디스크 숫자가 n1, cur + 1 숫자가 n2일 때 최소 디스크 회수로 하였습니다.

고려사항 : 최대 3개의 디스크를 한번에 돌릴수 있고 최대 3칸까지 한번에 돌릴 수 있음

2. calc(int cur, int n1, int n2) 설명.

현재 위치 cur의 숫자가 n1이고 password의 숫자가 d1일때 왼쪽으로 회전해서 d1으로 갔을때의 횟수. 오른쪽으로 회전해서 d1으로 갔을때의 횟수 둘중 작은 값을 우선 구합니다.

예를 들어 n1의 값이 7이고 d1이 1인 경우 7 -> 8 -> 9 -> 0 -> 1 이렇게 왼쪽으로 돌리는 경우와 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1이렇게 오른쪽으로 돌리는 경우 둘중 작은 값으로 현재 위치의 회전수를 구하게했습니다.

이렇게 구한 횟수를 현재의 디스크만 돌린 경우. 두개의 디스크를 같이 돌린 경우. 세개의 디스크를 같이 돌린 경우

세개 중 가장 작은 횟수를 dp에 저장하게 하였습니다.

어떤 부분이 잘 못 된 것인지 여러 조언 주시면 정말 감사하겠습니다.

#include <stdio.h>

#define INF 0x7fffff
#define MAXN 100
#define MAXD 10

int min(int a, int b) { if (a < b) return a; else return b; }
int abs(int a, int b) { if (a > b) return (a - b);  else return (b - a); }

int N;
char s[MAXN + 1];
int key[MAXN + 1];
int pwd[MAXN + 1];
int MEMO[MAXN + 1][MAXD + 1][MAXD + 1];


int calc(int cur, int n1, int n2)
{
	int ret, mn, diff, diff1, diff2, temp_n1, temp_n2, lturn, rturn, turn;

	if (cur == N) {
		return 0;
	}

	if (cur < (N - 3) && MEMO[cur][n1][n2] != INF)
		return MEMO[cur][n1][n2];

	mn = INF;
	diff1 = pwd[cur] - n1;
	lturn = (((diff1 + 10) % 10) / 3);
	lturn += (((diff1 + 10) % 10) % 3);

	diff2 = n1 - pwd[cur];
	rturn = (((diff2 + 10) % 10) / 3);
	rturn += (((diff2 + 10) % 10) % 3);

	if (lturn < rturn) {
		diff = diff1;
		turn = lturn;
		temp_n1 = ((n2 == -1) ? -1 : (n2 + diff + 10) % 10);
		if (cur <= N - 3)
			temp_n2 = (key[cur + 2] + diff + 10) % 10;
	}
	else {
		diff = diff2;
		turn = rturn;
		temp_n1 = ((n2 == -1) ? -1 : (n2 - diff + 10) % 10);
		if (cur <= N - 3)
			temp_n2 = (key[cur + 2] - diff + 10) % 10;
	}

	if (cur > (N - 3))
	{
		ret = (calc(cur + 1, temp_n1, -1) + turn);
		mn = min(ret, mn);

		ret = (calc(cur + 1, n2, -1) + turn);
		mn = min(ret, mn);
		return mn;
	}

	ret = (calc(cur + 1, temp_n1, temp_n2) + turn);
	mn = min(ret, mn);

	ret = (calc(cur + 1, temp_n1, key[cur + 2]) + turn);
	mn = min(ret, mn);

	ret = (calc(cur + 1, n2, key[cur + 2]) + turn);
	mn = min(ret, mn);
	MEMO[cur][n1][n2] = min(mn, MEMO[cur][n1][n2]);


	return MEMO[cur][n1][n2];
}

void init_memo()
{
	for (int i = 0; i <= N; i++)
		for (int j = 0; j < MAXD; j++)
			for (int k = 0; k < MAXD; k++)
				MEMO[i][j][k] = INF;
}

void get_input()
{
	scanf(" %d", &N);
	scanf(" %s\n", s);
	for (int i = 0; i < N; i++)
		key[i] = s[i] - '0';

	scanf(" %s\n", s);
	for (int i = 0; i < N; i++)
		pwd[i] = s[i] - '0';
}

int main()
{
	int i, j, k, ret;

	get_input();
	init_memo();
	
	ret = N;
	if (N >= 2)
		ret = calc(0, key[0], key[1]);
	else
		ret = calc(0, key[0], -1);
	printf("%d\n", ret);

	return 0;
}

zlzmsrhak 7년 전 2

이 부분이 잘못된 거 같습니다.

이렇게 구한 횟수를 현재의 디스크만 돌린 경우. 두개의 디스크를 같이 돌린 경우. 세개의 디스크를 같이 돌린 경우
세개 중 가장 작은 횟수를 dp에 저장하게 하였습니다.

디스크를 돌릴 때 1개, 2개, 3개를 같이 돌리는 경우가 조합될 수도 있기 때문에,

(예를 들어 1개 1번, 2개 1번, 3개 한번 이런식으로)

사실상 가능한 모든 돌리는 조합을 다 해봐야 합니다.

입력 받을 때, "" 안에 \n 이나 띄어쓰기 같은게 들어가 있으면 문제가 생길 수 있으니 빼주세요

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

문제

문제

출처

ICPC

1514 자물쇠 질문 드립니다.

hbh1107 7년 전 0

zlzmsrhak 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말