글 읽기 - 반례가 존재하는지에 대해 궁금해서 질문올려봅니당

gktgnjftm 5년 전 0

79번째줄의 hab[i]!=0을 i<here로 바꾸면 맞는데,

어차피 둘다 똑같다고 생각을 하고 코딩을 했었습니다.

왜냐하면, 모든 인구는 최소 1이 들어오기 때문에, 어떻게든 인구를 더해서 나눈다고 해도, 무조건 1이상이 나오기 때문에

인구수가 0을 만나기 전까지 체크를 했었습니다. 그래야 더이상 인구가 없으므로 진행을 하지 않는거라고 생각을 했는데

이게 혹시 데이터에 0이 들어오는 값이 주어지는 건가 궁금해서 올려봅니다(문제에는 그런조건은 없습니다)

(0이 들어온다는 가정이면 저 코드는 틀린게 맞다고 생각합니다)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <string>
#include <math.h>
#include <set>
#include <list>
#include <climits>
#include <string.h>
#include <deque>
#include <functional>
#include <stack>
using namespace std;
typedef long long ll;
#define INF 1000000000
#define mod 1000000007
typedef pair<int, int> P;
typedef pair<pair<int, int>, int> PP;
typedef pair<int, pair<int, int>> PPP;
int gox[4] = { 0,1,-1,0};
int goy[4] = { 1,0,0,-1};
int n, l, r;
int board[55][55];
bool visited[55][55];
int check[55][55];
int here;
void go(int x, int y) {

	visited[x][y] = true;
	check[x][y] = here;
	for (int i = 0; i < 4; i++) {
		int nx = x + gox[i];
		int ny = y + goy[i];
		if (nx < 1 || nx>n || ny<1 || ny>n) continue;
		if (visited[nx][ny]) continue;
		if (abs(board[x][y] - board[nx][ny]) >= l && abs(board[x][y] - board[nx][ny]) <= r) {
			go(nx, ny);
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &l, &r);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf(" %d", &board[i][j]);
		}
	}

	int cnt = 0;
	while (1) {
		memset(visited, false, sizeof(visited));
		memset(check, false, sizeof(check));
		here = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (!visited[i][j]) {
					go(i, j);
					here++;
				}
			}
		}
		if (here==n*n+1) break;
		else { // 인구이동을 시작한뒤에 다시 진행
			int hab[2505] = { 0, };
			int temp[2505] = { 0, };
			vector<vector<P>> h;
			h.resize(here + 1);
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					hab[check[i][j]] += board[i][j];
					temp[check[i][j]]++;
					h[check[i][j]].push_back({ i,j });
				}
			}
			for (int i = 1; hab[i]!=0; i++) { // 각단지에 들어가야하는 인구들
				hab[i] = hab[i] / temp[i];
			}
			// 다시 움직여주기
			for (int i = 1; i <here; i++) {
				for (int j = 0; j < h[i].size(); j++) {
					int nx = h[i][j].first,ny=h[i][j].second;
					board[nx][ny] = hab[i];
				}
			}
			cnt++;
		}
	}
	printf("%d\n", cnt);
	return 0;
}

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

문제

문제

출처

ICPC

반례가 존재하는지에 대해 궁금해서 질문올려봅니당

gktgnjftm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말