글 읽기 - [1713 후보 추천하기] 구현의 어느 부분이 잘못된 것일까요?

tofhddl9 2년 전 0

학생번호, 마지막으로 추천받은 순서, 득표수 를 가진 구조체 'cand'를 정의하고

나머지는 문제에서 요구하는대로 구현하였습니다.

쉬운 문제인데 어느 부분을 놓치고 있는지 모르겠네용..

#include <cstdio>

typedef struct candidate {
	int num;  //학생 번호
	int last; //마지막으로 추천받은 순서
	int voted;//득표 수
}cand;

cand st[22];
bool posted[101]; // 현재 게시되어 있는지
int n, m, num, idx, mn_voted, mn_last, cnt;

void update(int num, int last)
{
	for (int i = 0; i < n; ++i) {
		if (st[i].num == num) {
			st[i].last = last;
			++st[i].voted;
			return;
		}
	}
}

void add(int num, int last)
{
	if (cnt < n) { // 비어있는 사진틀이 존재
		++cnt;
		for (int i = 0; i < n; ++i) {
			if (st[i].num == 0) { //st[i]는 첫 번째로 비어 있는 사진틀
				st[i] = {num, last, 0};
				posted[num] = true;
				break;
			}
		}
	}
	else { // 비어있는 사진틀이 존재하지 않음
		mn_voted = st[0].voted;
		mn_last = st[0].last;
		idx = 0;
		for (int i = 1; i < n; ++i) { 
			if (st[i].voted < mn_voted) { //1순위, 최저 득표수
				mn_voted = st[i].voted;
				idx = i;
			}
			else if (st[i].voted == mn_voted) { //2순위, 득표 수가 같을 경우 오래된 순
				if (st[i].last < mn_last) {
					idx = i;
					mn_last = st[i].last;
				}
			}
		}
		posted[st[idx].num] = false;
		st[idx] = {num,last,0};
		posted[num] = true;
	}
	
}

int main()
{	
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; ++i) {
		scanf("%d", &num);
		if (posted[num]) update(num, i); //이미 게시되어 있다면 voted, last 갱신
		else add(num, i); //사진틀에 없는 학생이라면 추가
	}
	for (int i = 1; i < 101; ++i)
		if (posted[i])
			printf("%d ",i);
	return 0;
}

tofhddl9 2년 전 1

두 가지 부분에 문제가 있었습니다.

"추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 게시된 지 가장 오래된 사진을 삭제한다." 라는
조건에 의해서 이미 게시되어 있는 st[i]의 last는 update()에서 갱신하면 안됩니다.
따라서 17번 줄을 삭제해야 합니다.
add()함수에서 st[i].voted가 mn_voted보다 작을 시 mn_last의 갱신이 빠졌습니다..
따라서 42번째 줄에 mn_last = st[i].voted;를 추가해야 합니다.

#include <cstdio>

typedef struct candidate {
	int num;
	int last;
	int voted;
}cand;

cand st[22];
bool is_cand[101];
int n, m, num, idx, mn_voted, mn_last, cnt;

void update(int num)
{
	for (int i = 0; i < n; ++i) {
		if (st[i].num == num) {
			++st[i].voted;
			return;
		}
	}
}

void add(int num, int last)
{
	if (cnt < n) {
		++cnt;
		for (int i = 0; i < n; ++i) {
			if (st[i].num == 0) {
				st[i] = {num, last, 0};
				is_cand[num] = true;
				break;
			}
		}
	}
	else {
		mn_voted = st[0].voted;
		mn_last = st[0].last;
		idx = 0;
		for (int i = 1; i < n; ++i) {
			if (st[i].voted < mn_voted) {
				mn_voted = st[i].voted;
                mn_last = st[i].last;
				idx = i;
			}
			else if (st[i].voted == mn_voted) {
				if (st[i].last < mn_last) {
					idx = i;
					mn_last = st[i].last;
				}
			}
		}
		is_cand[st[idx].num] = false;
		st[idx] = {num,last,0};
		is_cand[num] = true;
	}
	
}

int main()
{	
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; ++i) {
		scanf("%d", &num);
		if (is_cand[num]) update(num);
		else add(num, i);
	}
	for (int i = 1; i < 101; ++i)
		if (is_cand[i])
			printf("%d ",i);
	return 0;
}

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

문제

문제

출처

ICPC

[1713 후보 추천하기] 구현의 어느 부분이 잘못된 것일까요?

tofhddl9 2년 전 0

tofhddl9 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말