글 읽기 - 안녕하세요. 반례의 경우를 못찾겠어서 질문 드립니다.

kimdaeho0513 6년 전 0

제가 코딩을 짯는데 어디서 반례가 생기는지 잘 모르겠습니다. 알려주시면 감사하겠습니다.

#include <iostream>
using namespace std;

int main()
{
	int man[100001][2];
	int tryx;
	int manx;
	int tryy[21] = {0};
	cin >> tryx;
	for (int i = 0; i < tryx; i++)
	{
		cin >> manx;
		for (int j = 0; j < manx; j++)
		{
			cin >> man[j][0] >> man[j][1];
		}
		for (int j = 0; j < manx; j++)
		{
			if (man[j][0] == 1)
			{
				for (int k = 0; k < manx; k++)
				{
					if (man[j][1] < man[k][1])
					{
						man[k][1] = 0;
						man[k][0] = 0;
					}
				}
			}
		}
		for (int j = 0; j < manx; j++)
		{
			if (man[j][1] == 1)
			{
				for (int k = 0; k < manx; k++)
				{
					if (man[j][0] < man[k][0])
					{
						man[k][1] = 0;
						man[k][0] = 0;
					}
				}
			}
		}
		for (int j = 0; j < manx; j++)
		{
			if (man[j][0] != 0)
			{
				tryy[i]++;
			}
		}

	}
	for (int i = 0; i < tryx; i++)
	{
		cout << tryy[i]<<endl;
	}
}

chogahui05 6년 전 0

반례가 생긴다는 차원에서 접근하면 안 되고

접근 방법 자체가 잘못되었습니다.

man[x][0]이 서류 점수고 max[x][1]이 면접 점수이지요?

근데 왜 man[j][0] == 1, man[j][1] == 1일 때에만 어떤 work를 수행하나요?

일단 이것부터가 문제이거니와..

조건을 만족시키면 man[k][??]의 값을 업뎃하네요?

답변을 하다 보면, 한 배열에 기능을 2개, 3개 넣어버리는 경우가 많더군요. 이건 설계 문젠데.

이것 때문에 잠재적인 문제가 발생하게 되고, 그걸 토대로 반례 케이스 재작성 하다 보면

역시나. 하면서 반례가 탁 하고 나오더군요.

chogahui05 6년 전 0

일단

(1) 알고리즘 설계 먼저 다시 하시고

(2) 기능 분리 시키세요.

그리고 반례 중에서 대표적인 거 하나만 간단하게 찾아봅시다.

답은 무엇이 되야 할까요?

kim님 소스 코드로는 4가 나오네요.

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

문제

문제

출처

ICPC

안녕하세요. 반례의 경우를 못찾겠어서 질문 드립니다.

kimdaeho0513 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말