[C 백준]실버 4/1940번 주몽

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

1940번: 주몽

 

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
 
int arr[15000];
 
int main() {
 
    int n, m;
    
    long sum = 0;
    int left= 0;
    
    int ans = 0;
    scanf("%d", &n);
    scanf("%d", &m);
    int right = n - 1;
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n-1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    
    //두개의 수만 가지고!
    while (left<right&&right<n) {
 
        if (arr[left] + arr[right] == m) {
            ans++;
            left++;
            right--;
        }
        else if (arr[left] + arr[right] > m) {
            
            right--;
        }
        else {
            left++;
 
        }
        
    }
 
    printf("%d", ans);
 
 
 
}
 

 

주입식으로 투포인터 푸는 방법을 외우면 문제점은 응용이 안된다는 거다.

그리고 무엇보다 문제를 안읽었다..ㅋ 원소 두개의 합으로 m이 되는 거였는데 난 원소 여러개의 합으로 m이 되는걸로 풀어서 처음에 틀렸다.

 

이 문제는 원소 두개의 합을 기준으로 왼쪽 오른쪽 포인터를 왔다리 갔다리 하는데 다른 문제들과 다른게 우선 정렬을 한다음에 왼쪽 포인터는 가장 처음에 오른쪽 포인터는 가장 끝에 놓는다. 

두개의 합이 s와 같으면 ans++을 해주고 왼쪽 포인터 ++ 오른쪽 포인터 --

두개의 합이 s보다 작으면 왼쪽 포인터 ++

두개의 합이 s보다 크면 오른쪽 포인터 --를 해준다.

 

 

반례

https://www.acmicpc.net/board/view/5087

글 읽기 - 1940 이거 도대체 왜 틀린거죠?

 

 

처음 썼던 코드

 

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
 
int arr[15000];
 
int main() {
 
    int n, m;
    
    int cnt = 0;
    int left= 0;
    int right = 0;
    int ans = 0;
    scanf("%d", &n);
    scanf("%d", &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
 
    while (true) {
        if (cnt >= m) {
            cnt -= arr[left++];
        }
        else if (right == n) {
            break;
        }
        else {
            cnt += arr[right++];
        }
        if (cnt == m) {
            ans++;
        }
    }
 
    printf("%d", ans);
 
 
 
}