글 읽기 - 오늘도 역시 질문을 남깁니다.

slanjdu 8년 전 0

전공이 아닌 알고리즘을 급하게 공부하니

사소한곳에서 실수가 너무 많은듯 합니다..

s에서 시작해서 g층에 도달할수 잇는지 보는것으로 문제를 이해하여서 큐를 구현하였고

-d,+u만큼 이동할수 있기에 감소할때는 1을 지나면 안되고 증가할때는 f를 넘지않게 구현하엿습니다. 그리고 g층에 도달하지 않았을시 flag 를 두어 도달하지 못하게 구현하였는데 틀렸다고 나오네요.. 고수님들의 피드백 부탁드립니다 .

#include<iostream>
using namespace std;

struct node
{
	int x;
	int cnt;
	struct node * next;
};

struct queue
{
	int size;
	node * front;
	node * rear;
};

queue * CreateQ()
{
	queue * Q = new queue();
	Q->front = NULL;
	Q->rear = NULL;
	Q->size = 0;
	return Q;
}

void Push(queue *Q, int x, int cnt)
{
	node * N = new node();
	N->x = x;
	N->cnt = cnt;
	N->next = NULL;

	if (Q->size == 0)
	{
		Q->front = N;
		Q->rear = N;
	}
	else
	{
		Q->rear->next = N;
		Q->rear = N;
	}
	Q->size++;
}

void Pop(queue *Q)
{
	if (Q->size == 0)
		return;
	node * temp = Q->front;
	Q->front = Q->front->next;
	delete(temp);
	Q->size--;
}

void DeleteQ(queue *Q)
{
	while (Q->size != 0)
		Pop(Q);
	delete(Q);
}

int a[1000005];
bool b[1000005];

int main()
{
	int f, s, g, u, d;
	cin >> f >> s >> g >> u >> d;
	queue * Q = CreateQ();
	Push(Q, s + u, 1);
	Push(Q, s - d, 1);
	int cnt = 0;
	bool flag = 0;
	while (Q->size != 0)
	{
		int x = Q->front->x;
		cnt = Q->front->cnt;
		b[x] = 1;

		Pop(Q);
		if (x - d >= 1 && b[x - d] == 0)
			Push(Q, x - d, cnt + 1);
		if (x + u <= f && b[x + u] == 0)
			Push(Q, x + u, cnt + 1);
		if (x == g && x >= 1 && x <= f)
		{
			cout << cnt << '\n';
			while (Q->size)
				Pop(Q);
			flag = 1;

		}
	}

	if (flag == 0)
		cout << "use the stairs" << '\n';
	return 0;
}

baactree 8년 전 1

일단 출발지점이 도착지점일때 못 찾겠네요

다음 부분은 다른사람이

koosaga 8년 전 2

1. 출발점이 도착지점일 때 못찾고

2. 방문한 정점이 큐에 여러번 들어가고 (= 시간 초과)

3. 정점을 방문할때마다 답이 찍히니 답이 틀리고..

큐를 제대로 구현하셨다면 이정도가 일단 문제점인거 같습니다.

koosaga 8년 전 1

+ 큐를 구현하실 줄 아신다면 std::queue를 배워보시는 것도 좋은 선택입니다. 코드가 훨씬 짧아집니다

baactree 8년 전 2

초기에 큐에 출발점만 넣기
    while(빌때까지){
    현재 큐 사이즈 만큼 반복{
        하나 팝;
        도착점이라면 리턴;
        아니면 위로 이동 가능?안 간곳?{
            가능하면 푸쉬;
            간곳 체크;
        }
        아래로 이동 가능?안 간곳?{
            가능 하면 푸쉬;
            간곳 체크;
        }
    }
    이동 ++;
}

slanjdu 8년 전 0

baactree 집에가서도 알고리즘을 하다니 넌 역시 대단해

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 지난번 한 실수 또 함

push하기전에 체크 했어야 했는데...

그거 안하고

시작점 이 도착지점일때 체크 안하고

두개 합치고

아까 처음에 넣었던 break<==디버깅할라고 뺏는데 다시 넣어서 패스 ㅋㅋㅋ

slanjdu 8년 전 1

koosaga 감사합니다 포인트만 딱딱 지적해주셧네요 ! 역시 대단하세요!

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

문제

문제

출처

ICPC

오늘도 역시 질문을 남깁니다.

slanjdu 8년 전 0

baactree 8년 전 1

koosaga 8년 전 2

koosaga 8년 전 1

baactree 8년 전 2

slanjdu 8년 전 0

slanjdu 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말