글 읽기 - 반례나 틀린점을 찾아주세요

plan222 3년 전 0

제가 생각하는 답은 다 나오고, 틀린점을 알아낼 수가 없어요.

gap에서 2K보다 크면 2K로 치는 이유는 a, z 이런걸 -a, z-로 바꿀 수 있기 때문이예요.

A문자가 B의 문자 바깥으로 나가게 되는 경우는, 그 나간 문자와 스페이스사이의 거리도 있고, B에 추가해야할 스페이스도 하나 늘어나기 때문에 2K로 고려했어요.

#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <set>

using namespace std;
int temp;
#define MIN(A,B) A<B?A:B;
#define MAX(A,B) A>B?A:B;
#define SWAP(A,B) {temp=A;A=B;B=temp;}
#define FOR(i,n) for(int i=0;i<(n);i++)

string A, B;
int K;
int d[2000][4000];

int gap(char a, char b) // ab의 차잇값. a와 b의 차이가 2K보다 크면 2K반환
{
	int tmp;
	tmp = a - b;
	if (tmp < 0)
	{
		tmp = -tmp;
	}
	if (tmp > 2 * K)
	{
		tmp = 2 * K;
	}
	return tmp;
}


int main()
{
	cin >> A >> B >> K;
	if (A.length() > B.length())  //A의 길이를 더 짧거나 같게 만들어줌.
	{
		swap(A, B);
	}

	for (int i = 0; i < A.length(); i++)
	{
		for (int j = 0; j < B.length() * 2; j++) //B의 길이의 2배인 이유는 i=0인 문자가 제일 오른쪽의 문자와 맞추는 경우도 고려해주기 위해. 
		{
			if (j == 0) //왼쪽을 밀려난 문자당 스페이스가 2개씩 증가하기 때문
			{
				d[i][j] = i * K * 2 + gap(A.at(i), B.at(j));
			}
			else if (j >= B.length()) //B의 바깥이면 그냥 2K로 계산
			{
				if (i == 0)
				{
					d[i][j] = MIN(2 * K, d[i][j - 1]);
				}
				else
				{
					d[i][j] = MIN(d[i - 1][j - 1] + 2 * K, d[i][j - 1]);
				}
			}
			else //일반적인 동적계획법
			{
				if (i == 0)
				{
					d[i][j] = MIN(gap(A.at(i), B.at(j)), d[i][j - 1]);
				}
				else
				{
					d[i][j] = MIN(d[i - 1][j - 1] + gap(A.at(i), B.at(j)), d[i][j - 1]);
				}
			}
		}
	}
	cout << d[A.length() - 1][2 * B.length() - 1] + (B.length() - A.length()) * K; //위에서 구한 거리 + 추가로 있는 스페이스까지.
}

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

문제

문제

출처

ICPC

반례나 틀린점을 찾아주세요

plan222 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말