[c++] 1940번: 주몽

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

1940번: 주몽

 

문제 요약

 

갑옷 재료에는 고유 번호가 있다.

두 재료의 고유 번호를 합쳐 M이 되면 갑옷이 만들어진다.

N개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있을까?

 

 

범위

 

재료의 개수 N (1 ≤ N ≤ 15,000)

갑옷을 만드는데 필요한 수 M (1 ≤ M ≤ 10,000,000)

고유 번호 (≤ 100,000)

 

 

---

 

 

이 문제는 입력받은 배열(재료의 고유번호)을 정렬해서 양 끝에서 부터 차례로 값을 합하고 비교하면서 진행하면 된다.

우선, 중첩 반복문을 사용해도 되는지 확인해보자.

시간 제한은 2초인 것을 보니 중첩 반복문을 써도 될 듯 싶은데, N의 최대값이 15,000 이므로 N^2은 시간 제한 내로 잘 돌아갈 것이다.

 

배열의 양 끝을 시작점으로 해서 안쪽으로 들어가면서 계산해준다.

//M = 9

1  2  4  5  8  10
↑              ↑
a              b
//x[a] + x[b] > M

1  2  4  5  8  10
↑           ↑
a           b
//x[a] + x[b] == M
//cnt++

1  2  4  5  8  10
   ↑     ↑
   a     b
//x[a] + x[b] < M

1  2  4  5  8  10
      ↑  ↑
      a  b
//x[a] + x[b] == M
//cnt++

// b < a -> 반복문 나옴

 

 

혹시나 있을 반례를 생각해보자.

반례는 대체로 문제를 잘 읽으면 생각할 수 있는 것들인데, 우선 재료는 고유한 수를 가지므로 중복된 값이 입력되지 않는다.

음.. 없는것 같군..^^

 

 

---

 

 

//1940번: 주몽
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, x[15002];

void input(){
    cin >> n;
    cin >> m;
    for(int i=0; i<n; i++) cin >> x[i];
}

void solution(){
    int cnt = 0, a = 0, b = n-1;
    
    while(b > a){
        if(x[a] + x[b] == m){ cnt++; a++; b--; }
        else if(x[a] + x[b] > m) b--;
        else                     a++;
    }
    cout << cnt << '\n';
}

int main() {
    ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    input();
    sort(x, x+n); //정렬 중요
    solution();
    return 0;
}

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!