글 읽기 - 아무리봐도 잘모르겠어요... 비쥬얼스튜디오로는 답잘나오는데 ㅠㅠ

gosupopdo 7년 전 0

bdp는 각줄에 블루로 바꾸는데 필요한 갯수(누적x)

wdp는 화이트가 필요한 누적수

rdp는 레드가되는데 수정해야하는 누적수

이걸 구해서 위에서 내려오는 ubdp[i-1]이랑 bdp[i]의 합 과 wdp[i]를 비교해서 더작은수를 ubdp에 넣고

마찬가지로 아래에서 올라오는 거는 dbdp[i+1]과 bdp[i]와 rdp[i]를 비교해서 dbdp[i]에 더 작은 수를 넣고

ubdp[i-1] + bdp[i]+ dbdp[i+1]의 가장적은수를 출력하게 했는데...

비쥬얼스튜디오로는 잘나옵니다. ㅠㅠ

#include <stdio.h>

#pragma warning(disable:4996)
int main() {
	int flag[50][50];
	int wdp[50], ubdp[50], dbdp[50], rdp[50], bdp[50];

	int n, m;
	int i, j;
	int min = 7777;
	int tmp;
	int cnt = 0;
	char a;
	freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	ubdp[0] = 7777;
	dbdp[n - 1] = 7777;
	for (i = 0; i < n; i++)
	{

		for (j = 0; j < m; j++)
		{
			scanf(" %c", &a);
			switch (a)
			{
			case 'W': flag[i][j] = 0;
				break;
			case 'B': flag[i][j] = 1;
				break;
			case 'R': flag[i][j] = 2;
			}
				printf("%d ", flag[i][j]);
		}
			printf("\n");
	}
	printf("\n");



	//////bdp구하는 과정
	for (i = 1; i <n - 1; i++)
	{
		cnt = 0;
		for (j = 0; j < m; j++)
		{
			if (flag[i][j] != 1)
				cnt++;
		}
		bdp[i] = cnt;

		printf("bdp %d %d\n", i, bdp[i]);
	}




	/////////wdp 구하는과정
	cnt = 0;
	for (i = 0; i < n - 2; i++)
	{
		for (j = 0; j < m; j++)
		{
			if (flag[i][j] != 0)
			{
				cnt++;
			}
		}
		wdp[i] = cnt;
		printf("wdp %d %d\n", i, wdp[i]);
	}



	cnt = 0;
	////////////////rdp 구하는과정
	for (i = n - 1; i > 1; i--)
	{
		for (j = 0; j < m; j++)
		{
			if (flag[i][j] != 2)
				cnt++;
		}
		rdp[i] = cnt;

		printf("rdp %d %d\n", i, rdp[i]);
	}




	//udbp 구하는 과정
	if (wdp[0] + bdp[1] < wdp[1])
		ubdp[1] = wdp[0] + bdp[1];
	else
		ubdp[1] = wdp[1];

	ubdp[0] = wdp[0];
	printf("ubdp 1 %d\n", ubdp[1]);
	for (i = 2; i <n - 2; i++)
	{
		if (ubdp[i - 1] + bdp[i] < wdp[i])
			ubdp[i] = wdp[i - 1] + bdp[i];
		else
			ubdp[i] = wdp[i];
		printf("ubdp %d %d\n", i, ubdp[i]);
	}






	//dbdp 구하는 과정

	if (rdp[n - 1] + bdp[n - 2] < rdp[n - 1])
		dbdp[n - 2] = rdp[n - 1] + bdp[n - 2];
	else
		dbdp[n - 2] = rdp[n - 2];

	dbdp[n - 1] = rdp[n - 1];
	printf("dbdp %d %d\n", n-2, dbdp[n-2]);
	for (i = n - 3; i >1; i--)
	{
		if (dbdp[i + 1] + bdp[i] < rdp[i])
			dbdp[i] = rdp[i + 1] + bdp[i];
		else
			dbdp[i] = rdp[i];
			printf("dbdp %d %d\n", i, dbdp[i]);
	}


	if (n == 3)
	{
		min = wdp[0] + bdp[1] + rdp[2];
		printf("%d", min);
		return 0;
	}

	for (i = 1; i < n - 1; i++)
	{
		tmp = ubdp[i - 1] + bdp[i] + dbdp[i + 1];
		printf(" %d %d\n", i, tmp);
		if (tmp < min)
			min = tmp;
	}
	printf("%d", min);
	return 0;
}

zlzmsrhak 7년 전 1

알고리즘에 문제가 있는 것 같습니다.

i번째에 파란색을 칠하고, 1~i-1중 파란색이 제일 아래 있는 경우가 처리되고, i+1~n 중 파란색이 제일 위에 있는 경우가 처리되면,

파란색이 최대 3줄인 경우만 처리됩니다.

반례입니다.

7 1

gosupopdo 7년 전 0

아 너무어렵네요 ㅠㅠ 문제나온지 얼마안되서 그런지 도움받을곳도없는데

어떤식으로 접근해서 푸셨는지라도 좀 알 수 있을까요??

zlzmsrhak 7년 전 1

아 대충보고 반례데이터도 맞길래 알고리즘 틀린 줄 알았는데 다시보니 알고리즘은 맞는 것 같네요.

102, 125번째 줄에 오타가 있는거 같은데 확인해보세요

gosupopdo 7년 전 0

아 오타고치니깐 맞았습니다 떳어요

감사합니다!!!!

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

문제

문제

출처

ICPC

아무리봐도 잘모르겠어요... 비쥬얼스튜디오로는 답잘나오는데 ㅠㅠ

gosupopdo 7년 전 0

zlzmsrhak 7년 전 1

gosupopdo 7년 전 0

zlzmsrhak 7년 전 1

gosupopdo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말