[백준] 3052번 : 나머지 - [C++]

 

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

3052번: 나머지

 

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

직전 문제인 숫자의 개수 문제를 푼다면 그리 어렵지 않게 풀 수 있는 문제다.

사실 문제 자체는 숫자의 개수와 거의 다르지 않고, 다만 나머지를 구해줄 뿐이니.. 그리 어렵지 않게 풀 수 있을 것이다.

 

혹시 해당 문제를 풀고오지 않았다면 아래 링크를 통해 먼저 풀어 보고 오시는 것을 추천한다.

 

https://st-lab.tistory.com/271

[백준] 2577번 : 숫자의 개수 - [C++]

 

 

 

 

 

앞서 우리는 숫자의 개수를 측정하고자 할 때 배열의 인덱스를 활용하여 사용했다.

이 번 문제도 마찬가지다.

 

10개의 입력받는 수에 대하여 각각 42로 나눈 나머지 값을 인덱스로 활용하여 배열의 값을 증가시키는 방식을 사용하면 된다.

 

 

그러면 42로 나눈 나머지가 갖을 수 있는 수는 0~41 이므로 42 크기의 배열을 선언해준 뒤, 해당 배열을 활용하면 되겠다.

그리고 10개의 입력에 대해 배열 값을 모두 증가시켰다면, 다시 한 번 배열을 순회하여 배열의 인덱스 중 1개 이상인 배열을 세어주면 된다.

 

사실 그렇게 크게 설명 할 건 없으니 주석과 함께 바로 문제를 풀이해보자.

 

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 2가지 입력 방법을 통해 성능을 비교해보려 한다.

배열 자체는 여기에선 int 형 배열을 사용할 것이지만, bool 배열 등으로도 사용 할 수 있으니 꼭 int 배열로 해주어야 할 필요는 없다. (서로 다른 수의 개수만 세어주면 되기 때문에...)

 

 

1. 기본 입출력

2. 향상 된 입출력

 

 

 

 

---

• 풀이

- 방법 1 : [기본 입출력]

 

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {

	/*
	  0으로 초기화를 해주어야 한다.
	  bool 배열을 활용 할 경우 bool count[42] = {false} 이런식으로
	  초기화 해줄 수 있다.
	 */
	int count[42] = {};	
	
	int v;
	for(int i = 0; i < 10; i++) {
		cin >> v;
		// 입력 받은 수를 42로 나눈 나머지 인덱스의 값을 증가시킨다.
		count[v % 42]++;	
	}

	int result = 0;
	/*
	  배열을 순회하면서 적어도 한 번 이상 나온 경우에는
	  result 값을 증가시킨다. (서로 다른 수를 세기 위함)
	 */
	for(int v : count) {
		if(v > 0) {		
			result++;
		}
	}
	cout << result;

	return 0;


}

 

 

그렇게 어렵지 않을 것이다.

 

 

---

- 방법 2 : [향상 된 입출력]

 

 

 

입력 방법을 향상 시킨 방법이긴 하나 이 번 문제는 워낙 입출력량이 적어 시간 차이가 나진 않을 것 같다.

 

 

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	/*
	  0으로 초기화를 해주어야 한다.
	  bool 배열을 활용 할 경우 bool count[42] = {false} 이런식으로
	  초기화 해줄 수 있다.
	 */
	int count[42] = {};	
	
	int v;
	for(int i = 0; i < 10; i++) {
		cin >> v;
		// 입력 받은 수를 42로 나눈 나머지 인덱스의 값을 증가시킨다.
		count[v % 42]++;	
	}

	int result = 0;
	/*
	  배열을 순회하면서 적어도 한 번 이상 나온 경우에는
	  result 값을 증가시킨다. (서로 다른 수를 세기 위함)
	 */
	for(int v : count) {
		if(v > 0) {		
			result++;
		}
	}
	cout << result;

	return 0;


}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 34137333  -  방법 2 : 향상 된 입출력

채점 번호 : 34137324  -  방법 1 : 기본 입출력

 

 

역시나 두 방식의 차이는 거의 나진 않는다.

---

• 정리

 

이 문제는 그렇게 어려운 점은 없었을 것이다. 

혹여 어렵거나 이해가 되지 않는 부분이 있다면 언제든 댓글 남겨주시길 바란다.