글 읽기 - 제가 어디를 놓치고 있는 걸까요?...ㅜㅜ

sls666 3년 전 0

주장: 29번 라인의now.s + now.c <= n, 이 조건이 없어야 하지 않을까요?

why: 클립보드의 이모티콘을 화면에 추가했을 때, 구하고자 하는 이모티콘의 개수보다 많아지는 경우에 대해서도 조건을 확인해주어야 최소시간을 구할 수 있지 않나하는 생각입니다. 다시 말해, 값이 n보다 커지는 경우, "화면에 있는 이모티콘 중 하나를 삭제한다"라는 방식에 의해 최소시간이 나오는 case가 존재할 거 같아 질문을 하게되었습니다. // 물론 위의 조건을 뺀다면, 값을 계속 큐에 넣기때문에 무한 루프를 돌것이라 생각하고 있습니다. 하지만, 얼마든지 n보다 커지는 상황에 대해서도 최소값이 나올 수 있지 않을까 하는 생각입니다.

#include <iostream>
#include <queue>
#include <cstring>
#define endl '\n'
#define MAX 1001
using namespace std;

struct Node {
	int s, c;
};

int n;
int d[MAX][MAX];  // d[i][j]: 화면의 이모티콘 개수가 i이고 클립보드의 이모티콘 개수가 j일때의 시간

int main() {
	cin >> n;  // 문제에서 S를 의미함
	memset(d, -1, sizeof(d));
	queue<Node> Q;
	Q.push({ 1, 0 });
	d[1][0] = 0;

	while (!Q.empty()) {
		Node now = Q.front();
		Q.pop();
		if (d[now.s][now.s] == -1) {
			d[now.s][now.s] = d[now.s][now.c] + 1;
			Q.push({ now.s, now.s });
		}
		if (now.s + now.c <= n && d[now.s + now.c][now.c] == -1) {  // <------------------- 이 부분
			d[now.s + now.c][now.c] = d[now.s][now.c] + 1;
			Q.push({ now.s + now.c, now.c });
		}
		if (now.s - 1 >= 0 && d[now.s - 1][now.c] == -1) {
			d[now.s - 1][now.c] = d[now.s][now.c] + 1;
			Q.push({ now.s - 1 , now.c });
		}
	}

	int ans = -1;
	for (int i = 0; i <= n; i++) {
		if (d[n][i] != -1) {
			if (ans == -1 || ans > d[n][i]) {
				ans = d[n][i];
			}
		}
	}
	cout << ans << '\n';


	return 0;
}

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

문제

문제

출처

ICPC

제가 어디를 놓치고 있는 걸까요?...ㅜㅜ

sls666 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말