글 읽기 - [18111] 반례를 찾습니다 ㅠㅠ

jeongbeen 3년 전 0

각 높이별로 블록이 몇 개 있는지 저장하고,

가장 낮은 층을 minn으로, 가장 높은 층을 maxx로 잡아줍니다.

minn ~ maxx 사이를 기준 k으로 잡아주면서

층(i)가 기준 k보다 높아서 inven에다가 넣어줄지

기준 k보다 낮아서 땅을 필요로 하는지(need)를 계산해주고

need <= inven 일 경우에만, ansheight랑 anstime을 비교해줍니다.

자꾸 틀렸습니다가 나와서 다른 분들의 코드를 참고해봤는데

같은 로직으로 푸신 분들이 계신걸 보니, 로직상의 문제는 아닌 것 같고

구현이 잘못된거같은데 못찾겠네요.. ㅠㅠㅠ

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
typedef pair<int, int> pi;

int arr[260];
int minn = INF, maxx = 0;
int main() {
	int n, m, b;
	scanf("%d%d%d", &n, &m, &b);

	for (int i = 0; i < n * m; i++)
	{
		int a;
		scanf("%d", &a);
		arr[a]++; //각 높이별 블록이 몇 개 있는지 저장함
		minn = min(minn, a); //가장 낮은 층
		maxx = max(maxx, a); //가장 높은 층
	}

	int anstime = INF, ansheight = 0;
	for (int k = minn; k <= maxx; k++)
	{
		if (arr[k] == 0) continue; //블록이 없는 경우 그냥 넘어감 == 해당 층이 없다는 뜻
		int need = 0, inven = b, time = 0; //need : 필요한 땅 , inven : 인벤토리에 있는 땅
		for (int i = minn ; i <= maxx; i++)
		{
			if (arr[i] == 0) continue;  //블록이 없는 경우 그냥 넘어감 == 해당 층이 없다는 뜻

			if (i < k) { //기준 층(k)보다 낮을 경우, 땅을 필요로함(need)
				need += (k - i) * arr[i]; //기준 층과의 차이 * 블럭 수
				time += (k - i) * arr[i];
			}
			else if (i > k) {
				inven += (i - k) * arr[i];
				time += (i - k) * arr[i] * 2;
			}
		}

		if (need <= inven) {
			if (anstime >= time) { //낮은 층부터 탐색을 하므로,
				anstime = time; //  같은 시간일 때 높은 층을 출력해야돼서 >=로 함
				ansheight = k;
			}
		}
	}

	printf("%d %d", anstime, ansheight);
}

jeongbeen 3년 전 0

if (arr[k] == 0) continue; //블록이 없는 경우 그냥 넘어감 == 해당 층이 없다는 뜻

if (arr[i] == 0) continue; //블록이 없는 경우 그냥 넘어감 == 해당 층이 없다는 뜻

해당 부분들을 없애주니 맞았습니다.

근데 왜 맞은건지는 아직도 모르겠네요 ㅠㅠ...

caritas1996 3년 전 0

블록이 없는 층이 최종적인 위치가 될 수 있어서 그런 것 같아요

jeongbeen 3년 전 0

감사합니다!!!!

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

문제

문제

출처

ICPC

[18111] 반례를 찾습니다 ㅠㅠ

jeongbeen 3년 전 0

jeongbeen 3년 전 0

caritas1996 3년 전 0

jeongbeen 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말