[백준/BOJ] 10810번 공 넣기 (C/C++)

백준 온라인 저지(BOJ) 10810번 공 넣기 

https://www.acmicpc.net/problem/10810

10810번: 공 넣기

* 사용언어 : C언어, C++

 

1. 문제

N개의 바구니가 있고 각 바구니에는 1개의 공만 넣을 수 있음

N개의 바구니는 1번부터 N번까지 번호가 적혀있는데, 입력에 따라 M번 공을 집어넣게 됨

각 회차마다 공을 넣는데, i번 바구니 부터 j번 바구니까지 k번 번호가 적힌 공을 넣음

(이미 공이 있는 경우 공을 빼고 새로운 공을 넣음)

M 번 반복 후 1번 바구니부터 N번 바구니까지 들어있는 공의 번호를 출력 (없으면 0 출력)

 

2. 풀이

구현 난이도에 비해서 문제 이해가 어려운 문제였습니다.

문제를 요약하면 다음과 같이 정리할 수 있습니다.

1) 공을 1개 씩 넣을 수 있는 바구니가 N개 있다. (1번 ~ N번)
2) 그리고 1부터 N까지 적혀있는 공이 있는데, 각 번호의 공은 모든 바구니를 채울 수 있을 만큼 많이 있다.
3) M번 반복하면서 공을 넣을건데, 주어진 입력에 따라 i부터 j까지 모든 바구니에 k가 적힌 공을 넣는다.

 

그리고 구현에 필요한 조건이 2가지 있는데

하나는 이미 공이 있는 경우 공을 빼고 새로운 공을 넣는다는 것이고,

또 다른 하나는 공이 들어있지 않은 바구니는 마지막에 0을 출력한다는 것 입니다.

 

크기가 N + 1 인 int 배열을 선언하고 (N번까지 처리하기 쉽게)

기존에 값이 있든 없든 그냥 k번을 덮어쓰면 됩니다.

 

코드 구현 자체는 단순하나, 배열 index 개념이 부족하면 헷갈릴 수 있는 문제입니다.

배열을 직접 손으로 그려보고 idx 가 1일 때 어떻게 처리되고, 2일 때는 어떻고, ... 를

하나씩 따져보면서 파악해보면 배열을 이해하고 사용하는데 도움이 될 겁니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <cstdio>

const int LM = 101;
int arr[LM];

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, m;
	scanf("%d %d", &n, &m);

	int i, j, k, idx;
	while (m--) {
		scanf("%d %d %d", &i, &j, &k);
		for (idx = i; idx <= j; ++idx) arr[idx] = k;
	}

	for (idx = 1; idx <= n; ++idx) printf("%d ", arr[idx]);
	return 0;
}

* 전역 변수로 int 형 배열을 선언하면 따로 초기화를 하지 않아도 됩니다. (0 으로 초기화됨)