배열 연습문제

출처 : https://blog.encrypted.gg/927

문제

여러 숫자가 주어졌을 때, 해당 숫자 중 2개를 골라 100을 만들 수 있는지 여부를 판단하여라

input

처음 주어지는 숫자는 전체 숫자의 개수(n <= 100)
나머지는 숫자 하나씩 주어진다.(각각의 수는 1이상 99이하의 수, 서로 다른 수가 주어짐)

5 
1 23 53 77 60

접근방법

• 카운팅 배열을 하나 더 둬서 더해서 100을 만들 수 있는지 여부를 판단한다.
  ex) 77을 판단할 때, 23이 있는지를 확인할 수 있도록한다.
  - 만약 23이 있으면 100을 만들 수 있다.
  - 만약 23이 없으면 77을 카운팅 배열에 추가한다.
• 위와 같이 풀면 입력 값(N)만큼의 시간복잡도로 문제를 풀 수 있게된다.

시간 복잡도 : O(N)

풀이

#include<iostream>
using namespace std;

int n;
int arr[100];

int main() {
	cin >> n;
    for(int i = 0; i < n; i++)
    	cin >> arr[i];
    int occur[100] = {};
    for(int i = 0; i < n; i++) {
    	if(occur[100 - arr[i]] == 1) {
        	cout << "100 만들 수 있음";
            return 0;
        }
        occur[arr[i]] = 1;
    }
    cout << "100 만들 수 없음";
    return 0;
}