글 읽기 - 테스트케이스 18일때 어떻게 8초가 나오나요?

kitri04 5년 전 0

현재 제 코드는 아래와 같습니다

bfs로 돌면서 탐색을 합니다.

arr 배열에는 해당 이모티콘 개수를 출력할 때 시간의 최솟값을 계속 지니고 있습니다.

테스트케이스에서는 18일 때 8초인데

제 프로그램에서는 10초가 나옵니다...

도움을 구해봅니다 ㅜㅜ

#pragma warning (disable:4996)
#include <bits/stdc++.h>
using namespace std;

int S;
int minTime = INT_MAX;
int arr[2002];
queue<tuple<int, int, int>> q;	// S개수, 복사수, 시간
void bfs()
{
	tuple<int, int, int> current;
	int currentSNum;
	int currentPNum;
	int currentTime;

	while (!q.empty())
	{
		current = q.front();
		currentSNum = get<0>(current);    // 현재 프린트 되어있는 개수
		currentPNum = get<1>(current);    // 현재 클립보드에 저장되어있는 개수
		currentTime = get<2>(current);    // 현재까지의 누적 시간
		q.pop();

		// 복사
		if (currentSNum != currentPNum)
			q.push(make_tuple(currentSNum, currentSNum, currentTime + 1));

		// 붙여넣기
		if (currentSNum <= S)
		{
			if (currentSNum + currentPNum == S)
			{
				if (arr[S] > (currentTime + 1))
					arr[S] = currentTime + 1;
			}
			else if (currentPNum != 0 && arr[currentSNum + currentPNum] > (currentTime + 1))
			{
				arr[currentSNum + currentPNum] = currentTime + 1;
				q.push(make_tuple(currentSNum + currentPNum, currentPNum, currentTime + 1));
			}
				
		}
			
		// 1개빼기
		if (currentSNum > 0)
		{
			if (currentSNum - 1 == S)
			{
				if (arr[S] > currentTime + 1)
					arr[S] = currentTime + 1;
			}
			else if (arr[currentSNum - 1] > (currentTime + 1))
				q.push(make_tuple(currentSNum - 1, currentPNum, currentTime + 1));
		}
	}
}

int main()
{
	scanf("%d", &S);

	q.push(make_tuple(1, 0, 0));
	fill(arr, arr + 2002, INT_MAX);
	arr[1] = 0;
	bfs();
	printf("%d", arr[S]);

	return 0;
}

djm03178 5년 전 3

복 - 붙 - 붙 - 복 - 붙 - 복 - 붙 - 붙

하면 됩니다.

kitri04 5년 전 0

감사합니다.

다른 글의 답변을 보니 클립보드의 개수도 고려해야 함을 알았습니다.

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

문제

문제

출처

ICPC

테스트케이스 18일때 어떻게 8초가 나오나요?

kitri04 5년 전 0

djm03178 5년 전 3

kitri04 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말