일부경우만 해보기

브루투 포스 문제를 계속 푸는중인데, 첨에는 일부 경우만 해보자하면 심장이 멎도록 고민을 해봤는데, 그냥 예외처리만 좀 해주면 되는거였다. 

 

1.수들의 합 문제:

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

2003번: 수들의 합 2

정답률은 50프로가 넘으므로 그렇게 어려운 문제는 아니지만, 한번에 맞췄다. 잘 없는일인데 신기하다. 내가 머리를 굴려서 뭔가 정답을 맞추면 기분이 이상하다.

#include <iostream>
using namespace std;

int a[10000];
int n;
long long m;
long long s[10000];

int main(){
    cin >> n >> m;

    long long temp = 0;
    int result = 0;

    for(int i = 0; i < n; i++){
        cin >> a[i];
        temp += a[i];
        if(a[i] == m){
            result++;
        }
        s[i] = temp;
    }

    
    // for(int i = 0; i < n; i++){
    //     if(a[i] > m){
    //         continue;
    //     }else if(a[i] == m){
    //         result++;
    //     }
    // }

    for(int i = 0; i < n; i++){
        if(s[i] < m){
            continue;
        }else if(s[i] == m && i != 0){
            // cout << "else if" << "\n";
            result++;
        }else{
            for(int j = 0; j < i-1; j++){
                if(s[i] - s[j] == m){
                    // cout << "else" << "\n";
                    result++;
                }else if(s[i] - s[j] < m){
                    // cout << "break" << "\n";
                    break;
                }
            }
        }  
    }

    cout << result << "\n";

    return 0;
}

 

우선 입력을 받으면서 a[i]값에 대해서 처리를 했다. 

a[i] > m : 답아님

a[i] = m: 답임 

 

 

그리고 합을 누적한 s[i]: 1~i까지의 합 을 이용해서 경우를 처리했다. 우선 자연수라는 것을 명심해야한다. 

s[i] < m : 이건 답이 될수없다. 그냥 지나간다  -> 왜냐하면 s[i]가 m 보다 작은데 그 일부인 j~i까지의 합이 m이 될수가 없다

s[i] = m 답이다. 이것도 이것만 구하면 여기다 다른값을 빼서 s[i]가 될수가 없다. 자연수라서 뭘빼면 무조건 더 작아지기만 한다.

s[i] > m 이건 경우를 따져봐야한다. (

     s[i]  - s[j] = m : 답이다. 그런데 i 랑 j가 1차이가 나면 s[i] - s[j] = a[i]라서 이미 위에서 처리해 준 값이다. 그래서 적어도 항상 두개값은 더한 상태이도록 범위를 지정했다. 

    s[i]  - s[j] <  m : 더 안해도 된다: j가 더 커지면 값이 더 작아지기 때문이다

    s[i]  - s[j] >   m: 계속 해본다.

 

 

 

 

2. 부분합: 정답률 25프로 정도

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

1806번: 부분합

#include<iostream>
using namespace std;

int n;
long long s;
int a[100000];
long long ss[100000];

int main(){

    cin >> n >> s;
    
    long long temp = 0;
    long long limit = 100000 * 10000;
    long long result = limit;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        temp += a[i];
        if(a[i] > s){
            result = 1; // 한개로 끝
        }
        ss[i] = temp;
    }

    if(result > 1){
        for(int i = 0; i < n; i++){
            if(ss[i] < s){
                continue;
            }else{
                for(int j = i-1; j >= 0; j--){
                    if(ss[i] - ss[j] >= s){
                        if(result > i-j){
                            result = i-j;
                        }
                        break;
                    }
                }
                if(ss[i] >= s){
                    if(result > i+1){
                        result = i+1;
                    }
                }
            }
        }
    }

    if(result == limit){
        cout << "0" << "\n";
    }else{
        cout << result << "\n";
    }
    
    return 0;
}

이 문제는 오히려 풀이는 앞문제랑 비슷해서 정답률에 비해서 딱히 어렵다 생각하면서 풀진 않았다. 그런데 문제였던건, 

 (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000) 범위 파악을 제대로 못해서 첨에 틀렸습니다 여러번 나오고 max로 나올수 있는 합도 잘못구했다. 

그리고 시간초과 나오는 부분을 개선하려다가 a[0]~a[i] 가 다 포함되는 경우를 누락시켜버려서 찾느라고 좀 해멨다. 

앞이랑 똑같다. 근데 시간초과 해결을 위해서는 i 와 가까운데서 부터 체크해 줘야한다. 

 

 

3. 소수의 연속합: 계속 시간초과 나옴~~

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

1644번: 소수의 연속합

*** 다시 했다

 

 

#include <iostream>
#include <vector>
using namespace std;

int n;
int a[4000001]; // 

vector <long long> v; 
vector <long long> s;

int main(){
    cin >> n;
    
    long long temp = 0;
    for(int i = 2; i < n + 1; i++){
        if(a[i] == 0){
            // cout << i << "\n";
            temp += i;
            v.push_back(i);  
            s.push_back(temp);           
            for(int j = i + i; j < n + 1; j = j + i){
                a[j] = 1; // 소수가 아니다
            }
        }
    }

    int result = 0;
    for(int i = 0; i < v.size(); i++){
        if(s[i] == n){
            result++;
        }
        for(int j = i-1; j >= 0; j--){
            if(s[i] - s[j] == n){
                result++;
                break;
            }else if(s[i] - s[j] > n){
                break;
            }
        }   
    }

    cout << result << "\n";
    
    return 0;
}

얘도 앞에 문제들이랑 똑같은데, 소수를 구하는 범위를 어제저녁에 미쳐버렸는지 8000000으로 해놨었다. 딱 구하기로한 숫자까지만 구하고 멈추도록 하면된다. 왜냐하면 자기보다 큰 소수는 구해봤자, 답이 못된다. (질문에서 준 n보다 큰 소수는 구할 필요가 없음)

 

그리고 다시 s를 활용한다! 앞에 문제랑 넘 똑같아서 그냥 이만 총총!

 

0427 - 0428