inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-O

3-O 질문있습니다

291

요가인

작성한 질문수 35

0

왜 틀렸는지 도저히 모르겠습니다..

 

#include <iostream>
#include <cstring>
using namespace std;

const int dy[2] = { 0,0 };
const int dx[2] = { -1, 1 };

int N, M, H, a, b, adj[31][21], visited[31][21], ret[21], cnt;
bool isOk;

void Print()
{
	cout << endl;
	for (int y = 0; y < 31; y++)
	{
		for (int x = 0; x < 21; x++)
			cout << adj[y][x];
		cout << endl;
	}
	cout << endl;
}

void Move(int y, int x, int start)
{
	if (y == H + 1)
	{
		ret[start] = x;
		return;
	}

	bool isDown = true;

	visited[y][x] = start;

	// 좌우 확인
	for (int i = 0; i < 2; i++)
	{
		int ny = y;
		int nx = x + dx[i];

		if (ny > H + 1 || nx <= 0 || nx > 2 * N - 1)
			continue;
		if (visited[ny][nx] == start)
			continue;
		if (adj[ny][nx] == 0)
			continue;

		Move(ny, nx, start);
		isDown = false;
	}

	if (isDown)
		Move(y + 1, x, start);
}

bool Check()
{
	// 값들 초기화
	memset(ret, 0, sizeof(ret));
	memset(visited, 0, sizeof(visited));

	for (int x = 1; x <= N; x++)
	{
		Move(0, x * 2 - 1, x * 2 - 1);
		if (ret[x * 2 - 1] != x * 2 - 1)
		{
			return false;
		}
	}

	return true;
}

void AddLadder()
{
	if (isOk)
		return;

	if (cnt >= 3)
		return;

	for (int y = 1; y <= H; y++)
		for (int x = 1; x < N; x++)
		{
			if (adj[y][x * 2] != 1 && adj[y][x * 2 - 2] != 1 && adj[y][x * 2 + 2] != 1)
			{
				adj[y][x * 2] = 1;
				cnt++;

				if (Check())
				{
					isOk = true;
					// Print();
					return;
				}
				AddLadder();

				adj[y][x * 2] = 0;
				cnt--;
			}
		}

	return;
}


int main()
{
	cin >> N >> M >> H;

	// 사다리 초기값
	for (int y = 0; y <= H + 1; y++)
		for (int x = 1; x <= N; x++)
			adj[y][x * 2 - 1] = 1;

	// 가로선 정보
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		adj[a][b * 2] = 1;
	}

	if (Check())
		cout << 0;
	else
	{
		AddLadder();
		if (cnt == 0)
			cout << -1;
		else
			cout << cnt;
	}

	return 0;
}

c++ 코딩-테스트

답변 1

0

큰돌

안녕하세요 가인님 ㅎㅎ

코드 나름 잘 짜셨는데요 ㅎㅎ

다만 코드가 잘못된 부분이 2가지가 있습니다.

 

먼저 해당 좌표마다 무조건 1부터 탐색을 하게 되면 너무나 비효율적입니다. 좌표를 매개변수로 넘기고 해당 매개변수부터 시작하게 바꿔주세요.

	for (int y = 1; y <= H; y++)
		for (int x = 1; x < N; x++)
		{
			if (adj[y][x * 

 

그리고 이부분인데요.

			if (adj[y][x * 2] != 1 && adj[y][x * 2 - 2] != 1 && adj[y][x * 2 + 2] != 1)
			{
				adj[y][x * 2] = 1;
				cnt++;

				if (Check())
				{
					isOk = true; 
					return;
				}

그러나 check() 가 먼저 되는 순간 무조건 그것이 글로벌한 최적해다. 그렇게 해서 빠져나온다고 되어있는데

그렇게 치면 예를 들어 이렇게 빨리 찾아서 3을 내뱉고 끝내겠죠.

|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|

|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|

|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|

 

하지만

|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|

|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|

|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|

이런 경우가 최적해인 경우는 알아차리지 못하지 않을까요? 즉 모든 경우의 수를 판단하지 못합니다.

이런 부분을 고쳐주시고 cnt를 아주큰 값에서 min으로 갱신될 수 있도록 바꿔주셔야 합니다.

최솟값은 최댓값부터 갱신시켜주시면서 만들어주셔야 해요.



또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

 

코딩살구클럽 가입부탁드립니다

0

27

2

코딩살구클럽 가입 요청 확인부탁드립니다

0

30

2

5-S 테스트 케이스 질문

0

35

2

코살 문제풀이 환경

0

48

2

2 - T 오큰수 문제가 있는 것 같습니다.

0

43

1

추천 추가문제들

0

43

2

프로그래머스 코테 환경 관련해서 질문드립니다.

0

47

2

해당 문제에 대한 채점이 코딩살구클럽에서 올바르게 처리되지 않습니다.

0

42

2

균형 이진 트리 설명 시 높이 숫자

0

31

2

4-H 질문드립니다.

0

35

2

1-K 질문드립니다.

0

41

2

대기업 인적성 시험 질문

0

41

2

4-C 질문드립니다

0

41

2

[수학숙제 / BOJ 2870] 채점 서버 오작동

0

37

1

코테 준비 질문

0

50

1

살구클럽가입 요청드려요

0

39

2

1-I 문제 질문

0

40

2

코딩살구클럽 가입

0

57

2

AI 코딩 도구 사용 시 학습 방법 조언

0

53

2

코딩살구클럽 오류

0

62

2

코살클 [3-F 괄호 추가하기] 프라이빗 9번 제보

0

46

1

코딩살구클럽 테스트 케이스 오류 제보

0

53

2

삼성 코딩테스트

0

65

2

틀린 이유를 못찾겠습니다

0

49

2