[백준 BOJ] 23057번 도전 숫자왕 (C++/cpp)

문제 설명

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

23057번: 도전 숫자왕

 

접근 방법 - 벡터를 응용한 브루트포스 알고리즘 문제

백준의 23057번 문제는 자료구조의 응용이 필요한 브루트포스 알고리즘 문제이다.

해당 문제는, 입력으로 주어진 숫자들에 대하여 1~sum(숫자들의 합) 사이에서 표현 불가능한 숫자의 개수를 구하여 출력하면 되는 문제이다.

문제에 있는 예제를 예시로 들어 설명하니, 문제 자체를 이해하지 못하였다면 아래 박스를 참고하면 될 것이다.

(ex1) 1 2 3   -> sum = 1+2+3 = 6
1부터 6까지의 숫자 표현 여부 >>
1 = 1
2 = 2
3 = 3
4 = 1+3
5 = 2+3
6 = 1+2+3
=> 모두 표현 가능하기 때문에, 표현 불가능한 숫자는 0개이다. 따라서 정답은 0이다.

(ex2) 1 3 4   -> sum = 1+3+4 = 8
1부터 8까지의 숫자 표현 여부 >>
1 = 1
2 표현 불가능 -> 카운트
3 = 3
4 = 4 = 1+3
5 = 1+4
6 표현 불가능 -> 카운트
7 = 1+3+4
=> 2와 6이 표현 불가능하기 때문에 정답에 카운트된다. 따라서 정답은 2이다.

필자의 경우에는, (모든 숫자들의 총합) - (각 숫자들의 합으로 표현 가능한 숫자의 모든 가짓수)로 정답을 구하였다.

탐색해야 할 숫자의 개수가 많지 않아서인지 걱정한 것과는 달리 시간 초과는 나지 않고 바로 성공하였다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 위의 설명과 아래의 코드 및 설명을 함께 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 입력으로 주어지는 숫자의 개수(n)를 입력받는다.

 

2) 숫자들의 합을 저장할 변수(sum)를 0으로 초기화하여 선언한다.

또한, 입력값으로 주어지는 숫자들을 저장할 벡터(v)를 선언하도록 한다.

 

3) n의 크기만큼, 반복문을 돌려 아래의 연산을 수행한다.

- 숫자(num)들을 하나씩 입력받도록 한다. 입력받는 대로, sum에 입력값만큼 더한다.

- 만일 벡터 v에 원소가 존재한다면, "현재 num에 v의 각 원소들을 더한 값"을 v에 순차적으로 추가하도록 한다.

- 벡터 v에 num의 값을 추가하도록 한다.

 

4) 3)의 입력 및 연산이 모두 완료되었다면, sort() 함수를 통해 벡터 v의 값들을 오름차순 정렬한다.

 

5) 벡터 v에 대하여, erase()와 unique()를 통해 중복된 값은 하나만 남겨놓게끔 연산을 수행한다.

 

6) 정답을 저장할 변수 result를 선언하고, "sum에 벡터 v의 크기를 뺀 값"을 해당 변수에 저장하도록 한다.

 

7) 최종적으로 저장된 result의 값을 정답으로 출력한 뒤, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 23057번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);   cout.tie(NULL);

	int n;
	cin >> n;
	
	int sum = 0;
	vector<int> v;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		sum += num;

		if (!v.empty()) {
			int size = v.size();
			for (int j = 0; j < size; j++) {
				int tmp = v[j] + num;
				v.push_back(tmp);
			}
		}
		v.push_back(num);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	int result = sum - v.size();
	cout << result << endl;
}

 

제출 결과

(2023.07.03 백준 23057번 문제 제출 결과)