바킹독 0x03 문제4 - 두 수의 합 / 백준 3273번

 

환절기는 위험하다.

목이 간질간질하다.

송진 때문인 줄 알았는데 아닌가..?

ㅋㅋㅋ모르겠다

약 먹고 자야겠다ㅎ

 

---

 

수열...

첫째 줄에 크기 n, 그다음에 수열들..

그다음에는 x 두 개 더했을 때 나와야 하는 값..

 

 

이중포문을 써도 되는가? 에 대해 좀 헷갈리는 게

n의 개수가 100000 10의 5승이라

N2 하면.. 개수 오버될 거 같기도 하고..

 

역시..

 

그럼 다른 방법이 뭐가 있을까..?

 

예전에 풀었던 식 중에

bool값을 써서

ture로 해놓고

x - 값 할 때 그 값이 true면 카운트했던 기억이 났다.

이 식을 도입.. 하기로 했는데 기억이 안 난다 ㅋㅋㅋㅋ

 

 

어찌어찌 머리 굴려서 써봤다.

 

흠..

몰랐는데 이런 경우는

범위 문제일 가능성이 있다고 했다.

 

범위라면.. a배열크기랑.. cnt 배열 크기인데..

 

cnt의 경우

값이 곧 인덱스이기 때문에

값인 x의 크기만큼 만들어 주어야 한다는 것이다.

 

헷갈려서 지 선생에게 물어보니

극단적으로 x가 2,000,000이고

a [i]가 1이면

결국 x - a [i]는 1,999,999인데

이게 cnt에 담겨야 하니까 오버되지 않게 200만을 맞춰줘야 한다는 것이다!.

 

그랬더니 런타임 오류는 안 났다.

 

그리고 곰곰쓰 생각해봄쓰

숫자에 중복이 있었쓰!!!!!!

그래서 그냥 /2 해줬다 ㅎ

 

답은 ㅎㅋ 내 마음대로 식이 되었다.

 

답지에는

 

밑에 식이 달랐다.

나는 모두 ture 로했는데..

여기는 조건을 걸고

다음에 true 해주었다.

 

나는 전자식이 더 좋다.

ㅎ 그렇다.

 

공간복잡도까지 고려한 답지에서는

int a[2000001]={};

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, t, x, ans=0;
  cin >> n;
  for (int i=0; i<n; ++i) {
    cin >> t;
    a[t]++;
  }

  cin >> x;
  for (int i = 1; i < (x+1)/2; ++i) {
    if (a[i]==1 && a[x-i]==1) ans++;
  }
  cout << ans;
}

어렵다..ㅋㅋ

 

/2는 알았는데..

왜 +1을 하나 했는데

x가 10일 때, 즉 짝수일 때는 (x+1)/2 해주면 답은 5 i는 1 2 3 4까지 검사한다.

(5,5)는 애초에 서로 다른 수라는 조건에 의해 맞지 않음 그래서 5를 검사할 필요가 없다는 것!

 

x가 11일 때, 즉 홀수일 때는 (x+1)/2해 주면 답은 6i는 1 2 3 4 5 가능!

(5,6) 검사가 되며 반대는 (6,5)는 5 범위 이상이라 패스

 

이래서 모든 쌍이 다 가능하다는 것!

 

특이하다.

 

여기는 애초에 bool값이라고 안 하고

int 0과 1로만 이루어지도록 설계한 거 같다.

 

답이 더 어렵다..

답이 더 어려워..