[백준 18114번] 블랙 프라이데이 (C++)

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

18114번: 블랙 프라이데이

알고리즘 분류에 보면 이분탐색이 들어가 있지만 본인은 투포인터 + 브루트포스로 풀었다.

일단 정렬한 배열의 처음과 끝을 투포인터로 잡았다.

그리고 투포인터로 잡은 상태에서 브루트포스를 돌려서 변수 3개를 설정했다.

x(처음), y(끝), i(for문)투포인터는 고정시키고 for문을 돌려서 각각 하나, 둘, 셋의 합이 C와 같으면 ans = 1로 설정했다.그리고 for문이 모두 끝나면 투포인터의 합이 C보다 작냐, 크냐를 기준으로 투포인터를 1씩 조정해주었다.

코드는 다음과 같다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;
int main(){
  int n, c, ans = 0;
  cin >> n >> c;
  int* weight = new int[n];
  for(int i = 0; i < n; i++){
    cin >> weight[i];
  }
  sort(weight, weight+n);

  int x = 0, y = n-1;
  while(x < y){
    if(ans) break;

    for(int i = 0; i < n; i++){
      if(i == x || i == y){
        continue;
      }

      if(weight[x] == c || weight[y] == c || weight[i] == c) ans = 1;
      else if(weight[x] + weight[y] == c) ans = 1;
      else if(weight[x] + weight[y] + weight[i] == c) ans = 1;

    }
    if(weight[x] + weight[y] < c) x++;
    else if(weight[x] + weight[y] > c) y--;
  }
  cout << ans;

}

 

 

 

 

처음 틀린건 실수로 투포인터를 조정하는 위치를 for문 안쪽으로 넣어버려서 틀렸다. 어렵지 않게 고쳤다.