빡대가리 인증

[SHEWANTSME]

this issue is for the fxxx idiot who couldn't even understand simple thing that 4 years old kid can do.

[SHEWANTSME]

백준 3052번

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

너의 ㅄ같은 풀이의 문제점은,, 42를 나눈 나머지를 새로운 배열에 for돌려서 넣는게 아니라,,

애초에 배열을 42사이즈까지 만들고, 42를 나눈 나머지가 인덱스가 되게 하고 그 값을 뭐 십이던 백이던 백만이던 넣어야

다시 42까지 FOR돌릴때 0이 아닌값만 카운팅해서 출력하면 되잖아

새로운 배열에 FOR돌리면, 이중FOR문을 써서 찾아야 하는데, 그게 또 경우마다 갈리더라고

일단 너의 틀린풀이

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int x,cnt=0;
    int cnt2 = 0;
    vector<int>v(10);
    vector<int>v2(1000);
    for (int i = 0; i < 10; i++) {
        cin >> x;
        v[i] = x % 42;
        v2[v[i]] = v[i];
    }
    for (int i = 0; i < 10; i++) {
        cout << v[i] << " " ;
    }cout <<""<< endl;
    for (int i = 0; i < 10; i++) {
        if (v[cnt] == v[i]) {
            cnt2++;
            cnt++;
        }
        else { cnt++; }
    }

    cout <<  cnt2 << endl;
}

아니 ㅅㅂ 이걸 왜 못푼거야

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int x,cnt=0;
    int cnt2 = 0;
    vector<int>v(10);
    int arr[42] = { 0, };
    for (int i = 0; i < 10; i++) {
        cin >> x;
        //v[i] = x % 42;  --> 개 병신같은 뻘짓
        //v2[v[i]] = v[i]; --> 왜 그러냐고 진짜
        arr[x % 42] = 2;
    }
    for (int i = 0; i < 42; i++) {
        if (arr[i]) cnt++;
    }
    cout <<  cnt << endl;
}

[SHEWANTSME]

백준 1546 평균

내가 왜 틀린지 모르겠음,, -> 맞왜틀 시전하는 실버 수준,,

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
   int n;
   double cnt = 0.0;
   int mx=-1;
   cin >> n;
   double arr[1000] = { 0.0, };

   for (int i = 0; i < n; i++) {
      cin >> arr[i];
      if (arr[i] > mx) mx = arr[i];
   }   
   for (int i = 0; i < n; i++) {
      arr[i] = (arr[i] / mx) * 100.0;
      //cout << arr[i] << endl;
      cnt += arr[i];
      //cout << cnt << endl;
   }
   double avg = cnt / n;
   cout << fixed;
   cout.precision(6);
   cout << avg << endl;

}

새로운 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
   int n;
   double cnt = 0.0;
   int mx=-1;
   cin >> n;
   double arr[1000] = { 0.0, };

   for (int i = 0; i < n; i++) {
      cin >> arr[i];
      if (arr[i] > mx) mx = arr[i];
      cnt += arr[i];
   }   
   cnt = (cnt / mx * 100)/n;
   cout << fixed;
   cout.precision(6);   
   cout << cnt << endl;
}

---

아 참고로 cout << fixed; 하고 cout.precision(6) 이라고 하면 소수점 이하 6자리까지 출력해주게 하는 놈임!

[SHEWANTSME]

백준 1712번

아니 진짜 별의별 경우의수 다 생각해서 했는데 그냥 a/(c -b) +1 해버리면 나오는거였다니,, 진짜 허망하다 ㅅㅂ

etc) 수익이 발생되는 부분을 알아보기 위하여 판매비용에서 가변비용을 뺀 이득값을 고정 비용으로 나누었다. 170 (노트북가격) - 70 ( 가변비용 ) - > 노트북 1대 팔았을때 생기는 차익 100만원 두대 팔면 200 3대팔면 300,,

그니까 c-b를 써먹었어야 했는데 ㅅㅂ while문이랑 숫자조작만 오지게 하니까 이런 생각을 못하지 등신아

내가 했던 풀이는 볼 가치도 없지만 올려봄

#include <iostream>
#include<algorithm>
using namespace std;
int main() {
    long long int a, b, c;
    cin >> a >> b >> c;
    long long int i = 1, t1 = 1,t2=1;
    if (b >= c) { cout << -1 << endl; 
    exit(0);
    }
    int mx = std::max(b, c);
    while (1) {
        if (mx / t1 != 0)t1 *= 10;
        else break;
    }
    //cout << t1 << endl; // mx보다 1자리수 더 크게 나옴

        while (1) {
            if (a / t2 != 0) t2 *= 10;
            else break;
        }
        cout << ((a / (t2 / t1) * 10))*(t2 / t1) / t1 * 10 + 1 << endl;

    //cout << t2 << endl;
    //long long int new_a = a / (t2 / t2) * 10;
    //cout << ((a / (t2 / t1) * 10))*(t2/t1)/t1*10+1<< endl;
    /*while (1) {
        if ((a / (t2 / t1) * 10) + b * (i) > c*i) i++;
        else break;
    }*/
    //cout << i << endl;
    //cout << (a / (t2 / t1) * 10) * i + 1 << endl;
    //cout << a/(t2/t1) *10 << endl;
    /*while (1) {
        if (a + b * (i) > c*i) i++;
        else break;
    }
    cout << i+1 << endl;*/

    return 0;
}

---

찐또 답

#include<iostream>
using namespace std;

int main(){
    long long int a, b, c;
    cin >> a >> b >> c;
    long long int i = 1, t1 = 1,t2=1;
    if (b >= c) { cout << -1 << endl; 
    exit(0);
    }
    else cout << a/(c-b) +1;
    return 0;
}

[SHEWANTSME]

백준 2869번 달팽이문제

이 문제도 1712번처럼 수식을 세워야 하는 문제임 나름 규칙을 찾았으나 내가 찾은 수식은 틀린수식,,

(c-b-1)/(a-b) + 1 을 해줘야댐,,

1시간동안 찾았는데 결국 틀린값,, 테케는 다 맞았는데 ㅅㅂ

암튼 답은 이거임..

#include<iostream>
using namespace std;
int main() { 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long int a, b, c,cnt=1;
    cin >> a >> b >> c;

    cout << (c - b-1) / (a - b)+1<< endl;

    return 0;
}

[SHEWANTSME]

백준 수학 부분은 진짜 ㅈ같애서 못해먹겠다.. 아니 뭐 반례 찾아도 틀려 ㅅㅂㅄㅄㅅㅅㅂ

[SHEWANTSME]

수학부분은 ㅈ같아서 일단 다음 파트인 재귀로 넘어옴..

이문제는 별찍기 10번인데 생각하기가 쉽지않음. 나중에 다시 리셋되고나서 풀어보면 와 개쬰당 이럴꺼야

#include<iostream>
using namespace std;

bool makestar(int x, int y) {

        if (((x % 3) == 1) && ((y % 3) == 1)) return 1;
        if (x == 0 || y == 0) return 0;
        return makestar(x / 3, y / 3);
    //  x = x / 3;
        //y = y / 3;

}

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (makestar(i, j)) cout << " ";
            else cout << "*";
        }
        cout << endl;
    }

    return 0;
}

[SHEWANTSME]

이번문제는 pie를 얼마나 정교하게 작성할 수 있느냐가 관건이였던 문제였음

#include <iostream>
#include <cmath>
#define PI 3.14159265358979
using namespace std;
double Original(int n) {

    return double (PI*n*n);

}
double Taxi(int n) {
    return 2 * n*n;

}

int main() {

    int n; cin >> n;
    cout << fixed;
    cout.precision(6);
    cout << Original(n) << endl;
    cout << Taxi(n) << endl;
    return 0;
}

---

이거 보면, pi를 대체 소수점 어디까지 정의해야 하느냐 때문에 ㅈㄴ 빡칠 수 있는데

cmath에 보면 삼각함수의 역함수에 대해 정의해둔 툴이 있다. arccos 이나 arcsin 을 써서 pie를 정의하면 풀린다고 한다.

arccos(-1)하면 파이가 나오고 아크사인은 또 정의역 수정해야 해서 귀찮으니까 그냥 저렇게 하면 되지 않을까?

[SHEWANTSME]

투포인터 관한 문제.

-> 솔직히 ㄹㅇ 그 어려운 투포인터가 아니고 그냥 ㅈㄴ 쉬운 투포인터임.

문제는 n값과 m값이 주어지고 그 사이즈들만큼의 배열이 있을 때, 걔네들 중에 겹치는애들만 출력하라는 내용

-> 강의에서는 따로 세번째 배열을 만들어서 풀이 했지만, 굳이 그렇게 할 필요가 없는게 어차피 오름차순 정렬이 되어있고 그놈들중에서 작은놈들부터 출력될텐데 굳이 따로 배열을 만들어서 for문을 다시 돌려야 하냐 이말이지.

암튼 투포인터 안쓰는 일반적인 이중 for문을 쓰면 다음과 같음

#include <algorithm>
#include <iostream>
using namespace std;
// 교집합 투포인터 알고리즘

int main() {
    int n; cin >> n;
    int x[30001];
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    int m; cin >> m;
    int y[30001];
    for (int i = 0; i < m; i++) {
        cin >> y[i];
    }

        // ORIGINAL 이중 FOR 사용방법 -> 위에서 sort는 빼주면 방법 같음
    int pointx, pointy;
    pointx = 0;
    pointy = 0;

    int ans[30001];
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (x[i] == y[j]) { ans[cnt] = x[i];  cnt++; }
        }
    }
    sort(ans, ans + cnt );
    for (int i = 0; i < cnt; i++) {
        cout << ans[i] << " ";
    }

    //이중for문을 피하려고 2pointer를 쓰는건데 왜 이중for문을 적어뒀냐?
    return 0;
}

숫자가 조금만 커져도 ㅈㄴ게 불안한 알고리즘임

하지만 이녀석은

#include <algorithm>
#include <iostream>
using namespace std;
// 교집합 투포인터 알고리즘

int main() {
    int n; cin >> n;
    int x[30001];
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    sort(x, x + n); // x배열 정렬
    int m; cin >> m;
    int y[30001];
    for (int i = 0; i < m; i++) {
        cin >> y[i];
    }
    sort(y, y + m);// y 배열 정렬
    int pointx = 0;
    int pointy = 0;
    int cnt = 0;
    // 2포인터는 두개의 배열이 정렬이 되어 있는 상태에서 사용할 수 있음.
    int ans[30001];
    while (pointx != n && pointy != m) {
        //(x[pointx] < y[pointy]) ? pointx++ : pointy++; -> 이건 리턴해주는 형식일때 쓰는거고,,, ㅄ아
        //if (pointx == n - 1 && pointy == m - 1) break; -> while(1)하고 while문 안에 if 얘를 쓰면 **무한루프**임 왜,,그런진?
        if (x[pointx] < y[pointy]) {
            pointx++;
        }
        else if (x[pointx] > y[pointy]) pointy++;
        else if (x[pointx] == y[pointy]) { cout<< x[pointx]<<" "; pointx++; pointy++; } // 이렇게 바로 출력하면 되지 않음? 걍

    }
    return 0;
}

[SHEWANTSME]

#include<iostream>
using namespace std;

int main() {

    int n; cin >> n;
    int ans = 0;
    int k;
    for (int i = n-1; i >=1; i--) {// i를 역순으로 하면 개수가 작은놈부터 출력 i를 정순으로 하면 개수가 많은놈부터 출력

        for (int j = 1; j < n - 1; j++) {
            if (i*(i + 1) - j * (j - 1) == 2 * n) {
                for (k = j; k < i; k++) {
                    cout << k << "+";
                }
                cout << i << " = " << n << endl;
            }
        }
    }

    return 0;
} // 이중 for라서 숫자 크면 노답임

#include<iostream>
using namespace std;

int main() {

    int n; cin >> n;
    int a = 2;

    while (a<n/2) {
        int jaritsu = a * (a + 1) / 2;
        if ((n - jaritsu) % a == 0 && n-jaritsu>-1) { // 강의듣고 짜본 코드
            for (int i = 1; i < a; i++) {
                cout << ((n - jaritsu) / 2) + i << " + ";
            }cout << ((n - jaritsu) / 2) + a << " = "<< n << endl;
        }
        a++;
    }

    return 0;
}

저게 왜 저렇게 실행이 되냐면

---

연속된 자연수의 합 계산하기!

입력값 15 15 에서 1과 2 빼기 -> 12에서 2를 나눈 나머지(2개 연속되는지 보는거임)

12%2 == 0 이자나 12/2가 6이자나

1 2 6 6

---

7 8 이런식으로 연속된 두 수의 합으로 나타낼 수 있지

연속된 3개는 어케구함? 15-1-2-3 = 9 9%3 == 0 이니까 9/3 = 3이자나

1 2 3 3 3 3

---

4 5 6

연속된 4개는? 15-1-2-3-4 = 5 5%4 !=0 패스

연속된 5개는?

15 - 1- 2- 3- 4 -5 = 0 0%5 == 0 0/5 = 0 1 2 3 4 5 0 0 0 0 0

---

1 2 3 4 5

이런식으로 구할 수 있음!

[SHEWANTSME]

이분탐색 HOW?

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

int main() {
    int n; cin >> n;
    int key; cin >> key;
    vector<int>vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end());
    int left = 0;
    int right = n - 1;
    while (left <= right) { // 같아도 루프가 진행은 되어야 하니까
        int mid = (left + right) / 2;
        if (vec[mid] == key) { cout << mid + 1 << endl; exit(0); }// 값의 인덱스를 출력하는게 목표니까
        else if (vec[mid] < key) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    return 0;
}

어렵지 않지?

두개의 변수 need

left, right 필요

left = 0 으로 초기화

right는 맨끝인덱스로 초기화

여기선 8개니까(값들이) right는 7이겠지

how do we 이분검색?

--> 일단 정렬이 되어 잇어야함!!!!!!!!!!!!! 무조건건건건

---

8 32 ( 8은 arrsize, 32는 key)

23 87 65 12 57 32 99 81

---

중간부분을 가르키는 변수 = mid

mid = (left+right) /2;

싹다 정수형이지

(0+7)/2 = 3.5 -> 3(int니까)

arr ={12,23,32,57,65,81,87,99};

그래서 arr[mid] 가 arr[3] 이니까 57을 가리킴

---

if(arr[mid] == key) cout << mid+1 <<endl;

else if(a[mid] >key){

right = mid; -> 근데 mid도 어차피 key 가 아니니까

right = mid-1까지 해도 될듯?

mid = (right+left) /2;

}

else{

left = mid; -> 얘도 마찬가지로 mid+1해도될듯

mid = `` 같이 해주면 나올껄? -> ㅇㅇ

}

랜선자르기! -> 백준 1654번

위의 이분탐색을 공부하고 뭐가 괜찮을까? 싶어서 도전한 1654번. 1시간은 더 걸린듯싶당

일단 맥락은 이분탐색과 흡사함. 아니 똑같음. 하지만, 이 문제는 parametric search여서

문제에 해당하는 조건들을 더 부합을 시켜야 만족된 값을 얻을 수 있는 문제였다.

일단 소스코드부터 보자면

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
long long already[10000];
int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    long long n; cin >> n;
    long long key; cin >> key;
    for (int i = 0; i < n; i++) {
        //cin >> vec[i];
        cin >> already[i];
    }
    sort(already, already + n);
    long long left = 1;
    long long right = already[n-1];
    long long ans;
    while (left <= right) { // 같아도 루프가 진행은 되어야 하니까
        long long mid = (left + right) / 2;
        long long cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt = cnt + (already[i] / mid);

        }
        if (cnt < key) {
            right = mid - 1;
        }
        else if (cnt >= key) {
            left = mid + 1;
            ans = mid;
        }

    }
    cout << ans << endl;
    return 0;
}

백준에 제출한 코드다. 근데 의문이 드는점들이 몇개 있다.

1. 아니 근데 꼭 right = mid-1 , left를 mid+1로 재정의 해야하나? 그냥 mid로 퉁치면 안됨?

--> 이것은 정말 위험한 발상이다. 왜 굳이 mid-1, mid+1로 하겠니? left랑 right이 같은 상황이면, mid도 left랑 right이랑 같은 값을 가지게 되는데, 그때 만약 cnt가 key보다 작으면!!
right가 mid 가 되고 다시 while문을 돌고 mid 는 (left+right )/2 가 되고, right 이 다시 mid 가 되고,, --> 답도없는 무한루프에 빠지게 된다!!

그래서 일부러 1씩 더해주고 빼주는거임!

2. 아니 왜 이렇게 되는거임? cnt==key 일때 따로 해줘야 하는거 아님?

   
   else if (cnt >= key) {
           left = mid + 1;
           ans = mid;
       }

(while문 밖임 ) cout << ans << endl;

이거는 문제에서 쓰이는 트릭임.  너가 원래 했던대로, 만약에

```python
if(cnt == key) cout << mid+1 << endl; 

이래버리면, cnt == key가 되는 mid중에 가장 최소값일 수도, 최대일수도, 그 중간일 수 도 있는 값을 출력하게됨 그래서 저 위에 코드처럼, cnt>= key 해주고 , 일단 left는 mid보다 1이 커지는데 그 이후에 left,mid,right 의 관계는 일단 치워두고!! cnt=key일때의 가장 큰 값인 mid 만 따로 빼오는거니까 가장 긴 선의 길이를 출력 할 수 있는 것이다 이말이야.

3. 아니 왜 right이 최소일때가 아니고 최대일때여야 함? 존나 짱나네

--> 990 839 1 이렇게 주어지면 min이 1이고 right가 1인데

그럼 뭐 해볼것도 없이 1이 나오기때문에,,, min으로 하면 안되고 max를 right으로 해줘야함.

시간이 줄어드는 건 원하는 대로 최솟값이 충분히 클 때뿐이고 ,

그마저도 최솟값이 최대의 반씩이나 되더라도 루프를 한 번 덜 돌 뿐임.

게다가 시간 측정은 전체 데이터 중 가장 오래 걸린 것을 기준으로 하니 최솟값이 작은 케이스가 하나라도 있다면 무용지물이 됩니다. 특정 케이스에서만 시간이 줄어드는 것은 문제를 통과하는 데에 거의 아무런 도움이 되지 못하고, 최악의 경우에 빨리 돌게 해야 시간이 줄어듭니다.

최악의 경우를 고려해야겠지요?

4. 근데 int 의 범위가 2의 31승-1까지고 (-2의 31승부터 2의 31승-1까지), 지금 랜선길이도 2의 31승-1까진데, 왜 int가 아니고 longlong 해야됨?

--> ㅄ아 mid 구할때 left + right/2 해야하는데 right이 2의 31승-1에다가 left가 2의 30승이면(최소값이) 그냥 씹씹씹 오버플로우인데 되겠냐?

---

뮤직비디오 문제.

43. 뮤직비디오(이분검색 응용) 지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지 되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기 로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다. ▣ 입력설명 첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다. 다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다. 부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자. ▣ 출력설명 첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요. ▣ 입력예제 1 9 3 1 2 3 4 5 6 7 8 9 ▣ 출력예제 1 17

솔직히 말하면 위에 문제랑 거의 똑같음. 차이점이라면, 얘는 최소값을 찾는거고 위에는 최대길이를 찾는거고.. 소스코드가 거의 비슷함. 생각하는 방식도 비슷하니 유의할것.

#include <iostream>
#include <vector>
using namespace std;
// ans = 1 부터 다 더한 값 사이에 있지. 
int main() {
    int n; cin >> n;
    int m; cin >> m;
    int right = 0;
    vector<int> v(n);
        int maxi = -21470000;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        right += v[i];
                if(v[i] >maxi) maxi = v[i];
    }
    int left = 1;
    int res;
    while (left <= right) {
        int mid = (left + right) / 2;
        int cnt = 1; int sum = 0;
        for (int i = 0; i < n; i++) {
            if (sum + v[i] > mid) {
                cnt++;
                sum = v[i];
            }
            else {
                sum += v[i];
            }
        }
        if (mid >= maxi && cnt <= m) {
            res = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    cout << res << endl;
    return 0;
}

[SHEWANTSME]

백준 10816 숫자카드2

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int arr1[500000];
int arr2[500000];
int ans[500000];
int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    long long n; cin >> n;
    for (long long i = 0; i < n; i++) {
        cin >> arr1[i];
    }
    sort(arr1, arr1 + n); // 첫번째 배열 정렬
    long long m; cin >> m;
    multimap <int, int>map;
    for (long long i = 0; i < m; i++) {
        cin >> arr2[i];
        map.insert(make_pair(arr2[i], i)); // 두번째 배열 원소 입력시 인덱스와 pair
    }
    sort(arr2, arr2 + m); // 두번째 배열 정렬
    int point1 = 0; // arr1 비교용
    int point2 = 0; // arr2 비교용
    int cnt = 0;
    bool check = false; // 같았던 적이 있는지 체크변수
    while (point1<n && point2<m) {
        if (arr1[point1] < arr2[point2]) point1++; 
        else if (arr1[point1] == arr2[point2]) {

            cnt++;
            if (point1 == n - 1) { // 마지막 원소까지 같은 경우일때
                ans[map.find(arr2[point2])->second] = cnt;  
            }
            point1++;
            check = true;

        }
        else if (arr1[point1] > arr2[point2] && check ==true) {
            ans[map.find(arr2[point2])->second] = cnt; 
            point2++;
            cnt = 0;
            check = false;
        }
        else if (arr1[point1] > arr2[point2] && check == false) {
            cnt = 0;
            point2++;
        }
    }

    for (int i = 0; i < m; i++) {
        cout << ans[i] << " ";
    }

    return 0;
}

진짜 고심해서 어렵게 만든 코드지만,, 치명적인 단점이 존재했다.

예를들어 4 -1 -3 0 0 5 -3 0 -1 0 2 같은 경우는 내 알고리즘에 따르면 1 2 1 0 0 이 나온다.

같은 값이 나왔을때 의 예외 처리를 못해주는건데,, ( 근데 좀만 잘 머리 굴리면 나올거 같긴 한데 지금상태로는 도저히 ㄴㄴ..)

그래서 맨 마지막에 같은 값들이 나왔을때 먼저나온값으로 초기화 하면 되겠다! 싶었지만

일단 같은 값을 찾는것부터가 이중for문 돌아서 시간초과걸림..

그래서 다른 방법을 고수해야하는데

그냥 미친척 이천만 배열 때려 박으면 젤 빠르기도 하고 쉽기도 하고 무지성이긴 하지만

그렇게 풀고싶지는 않았기에 다른 코드들을 봤다.

unordered map 을 이용하여 풀면 진짜 지나가던 초딩도 풀수 있을 정도로 간단했다. 이 문제에서는 set을 쓰면 시간 초과가 뜬다고 한다. 그래서 map위주로 하는데 순서가 정렬되지 않는 unordered를 써야 이렇게 할 수 있다.

#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> mp;
int n, m;
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i;
    cin >> n;
    for (i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        mp[temp]++; // 맵에 temp만큼의 인덱스가 쁠쁠됨
    }
    cin >> m;
    while (m--) {
        int target;
        cin >> target;
        cout << mp[target] << " "; // 타겟의 인덱스를 넣으면 아까 temp인덱스의 짝을 출력하는거니까
 // 아니 이렇게 간단히 풀린다고?? ㅡㅅㅡ
    }
    return 0;
}

[SHEWANTSME]

백준 1644번

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

내가 골드를 내힘으로 풀다니,, 감격에 눈물이 흐른당.,

암튼 조그마한 문제가 있는 내 풀이를 보자면 이렇다.

#include <iostream>
#include <algorithm>
#include <cmath>
int arr[4000000];
int newarr[4000000];
int cnt = 0;
bool ch=false;
using namespace std;
void findsosu3(int n) {
    for (int i = 2; i <=n; i++) {
        arr[i] = i;
    }
    for (int i = 2; i <= n; i++) {
        if (arr[i] == 0) continue;
        for (int j = 2 * i; j <= n; j = j + i) {
            arr[j] = 0;
        }
    }
    for (int i = 2; i <= n; i++) {
        if (arr[i] != 0) { 
            newarr[cnt] = arr[i];
            cnt++;
        }
        if(arr[i]==n) ch = true;
    }
    int left = 0;
    int right = 1;
    int newcnt = newarr[left] + newarr[right];
    right++;
    int ans = 0;
    bool check = false;
    while (left < right&& right<cnt) {

        if (newcnt  < n) {
            newcnt += newarr[right];
            right++;
        }
        else if (newcnt >= n) {
            left++;
            right = left + 1;
            if (newcnt == n) {
                ans++;
            }
            newcnt = newarr[left] + newarr[right];
            right++;
        }
    }
    if (ch == true) {
        cout << ans + 1 << "\n";
    }
    if(ch==false){
        cout << ans << "\n";
    }
}
int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n; cin >> n;
    if (n == 1) cout << 0;
    else if (n == 2) cout << 1;
    else if (n == 3) cout << 1;
    else findsosu3(n);
    return 0;
}

굉장히 지저분하지만,, 어찌어찌 풀리긴 했당..

다른분들의 깔끔한 풀이를 보자면

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

int n;
vector<int> primeN;
bool arr[4000001];
int sum;
int cnt;

int main(){
    cin>>n;
    if(n == 1){
        cout<<"0";
        return 0;
    }
    // 에라토스테네스의 체
    for(int i=2; i<=n; i++){
        if(arr[i])  continue;
        for(int j=i+i; j<=n; j+=i){
            arr[j] = true; // not prime number
        }
    }
    for(int i=2; i<=n; i++){
        if(!arr[i]) primeN.push_back(i);
    }

    int start = 0, end = 0;
    sum = primeN[start];
    int pSize = primeN.size();
//    primeN.push_back(0);
    while (end < pSize) {
        if(sum == n){
            cnt++;
        }
        if(sum >= n){
            sum -= primeN[start];
            start++;
        }
        if(sum < n){
            end++;
            sum += primeN[end];
        }
    }
    cout<<cnt<<"\n";
}

내가 아까 푼 1644번의 가장 깔끔한 풀이이다.

내가 포인터를 설정한거랑 다른점이 뭐냐면(실은 대부분 사람들이 이렇게 품)

나는 포인터 left right 이 붙어있었고 포인터들의 합이 결국 n 을 만족했을때 left랑 right 을 갱신시켰다는점이다(left 한칸옆 right은 left 한칸옆 )

근데 이게 단점이 뭐냐면 이미 n과 같은 지점에서 그 값을 재사용할 수 없어서 메모리를 더 쓴다는 점이다. 나는 l이랑 r을 다시 사용 안하고 새로운 값으로 초기화 시켰는데

그럴 필요가 없는게 그 상태에서 만약 값이 크거나 같으면 left 를 한칸 땡겨서 다시 계산하고 작으면 right을 땡기면 됨!!

위의 코드를 보면 이해가 갈것임!

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
vector <int> primes;
vector <bool> check;
int main()
{
    int i,j;
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    check.resize(n+1,true);
    for(i=2;i*i<=n;i++){
        if(!check[i]) continue;
        for(j=i*i;j<=n;j+=i){
            check[j]=false;
        }
    }
    for(i=2;i<=n;i++){
        if(check[i]) primes.push_back(i);
    }
    int res=0,sum=0,l=0,h=0;
    while(1){
        if(sum>=n) sum-=primes[l++];
        else if(h==primes.size()) break;
        else sum+=primes[h++];
        if(sum==n) res++;
    }
    printf("%d",res);
    return 0;
}

이것도 비슷한 풀이.

아직도 어려운 알고리즘의 세계다..

[SHEWANTSME]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//int Aarray[30];
//int Barray[30];
//int put[30];
vector<int> item;
vector<int> front;
vector<int> back;
int result = 0;
int n, c;
void MakeSum(int idx, int num, int sum, vector<int>&v);

int main() {
    cin >> n;
    cin >> c;
    if (n == 1) {
        int k;
        cin >> k;
        if (k > c) {
            cout << 1 << "\n";
        }
        else cout << 2 << "\n";
    }
    else {
        for (int i = 0; i < n; i++) {
            int alpha; cin >> alpha;
            item.push_back(alpha);
        }
        MakeSum(0, n / 2, 0,front);
        MakeSum(n / 2, n, 0,back);
        sort(front.begin(), front.end());
        sort(back.begin(), back.end());

        int left = 0;
        int right = back.size() - 1;
        while (true) {
            //front을 모두 체크 했을때
            if(left == front.size()) break;
            //back을 모두 체크 했을때
            if (right == -1) break;

            if (front[left] + back[right] <= c){
                result += (right +1); //front[left]와 합쳐서 합이 c이하가 되는것은 back의 right 인덱스 이하의 것들 모두 가능하다
                left++; //다음에 확인할 front의 인덱스
            }

            else right--;
        }
        cout << result << "\n";
    }

    return 0;
}

void MakeSum(int idx, int num, int sum, vector<int>&v) {
    //합이 C를 넘어갈때
    if (sum > c)return;

    //앞쪽 끝까지 체크 했을때
    if (idx == num) {
        v.push_back(sum);
        return;
    }

    //index구간 물건을 고를때
    MakeSum(idx + 1, num, sum + item[idx], v);

    //index구간 물건을 고르지 않을때
    MakeSum(idx + 1, num, sum, v);

}

이해는 가는데,, ㅈㄴ 구현을 못해먹겠다 혼자서.. 나중에 풀어보자.. ㅅㅂ

[SHEWANTSME]

백준 11053 가장긴 증가하는 부분수열 1

이문제가 생각보다 어려운게 , DP를 어떤식으로 만들어야 하는지 생각이 오래걸림

#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;
int main() {
    int n; cin >> n;
    int res = 1;
    vector<int> arr(n + 1), dp(n + 1); // ARR랑 DP 배열 생성

    for (int i = 1; i <= n; i++) {
        cin >> arr[i]; // ARR를 CIN 함
    }
    dp[1] = 1; // MIN을 1 로 해야함 ( 길이니까)
    for (int i = 2; i <= n; i++) { 
        int max = 0;
        for (int j = 1; j <i; j++) {
            if (arr[j]<arr[i] && dp[j]>max) {
                max = dp[j];
            }// DP가 MIN이 1인데 MAX가 0 이니까 일단 초기화됨
        }
        dp[i] = max + 1;// DP[I]가 DP[J]보다 크니까 맥스에다가 1 증가
        if (dp[i] > res) res = dp[i];
    }
    cout << res;
//RES초기화를 처음에 1 로 안하고 0으로 하면 
// N이 1일때 엉뚱한 0이 튀나오기때문에 RES를 1 로 초기화시킨거임

    return 0;
}

백준 가장 긴 증가하는 부분수열 2 (12015번)

#include<iostream>
#include<algorithm>
using namespace std;
int arr[1000001];
int dp[1000001];

int LowerBound(int *arr, int value, int arrLength) {
    int low = 1;
    int high = arrLength;
    while (low < high) {
        int mid = (low + high)/ 2;
        if (value <= arr[mid]) high = mid;
        else low = mid + 1;
    }
    return low;
}
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    dp[1] = arr[1];
    //(arr[1] < arr[2]) ? dp[2] = arr[2] : dp[1] = arr[2];
    int i = 2;
    while (i<=n) {
        if (dp[i - 1] < arr[i]) {
            dp[i] = arr[i];
        }
        else {
            if (arr[i] > 0) {
                //dp[i] = arr[LowerBound(arr, arr[i], i)];
                //dp[i] = arr[LowerBound(arr, arr[i], i)];
                dp[LowerBound(arr, arr[i], i)] = arr[i];

            }
        }

        i++;
    }
    for (int j = 1; j <i; j++) {
        if(dp[j]!=0) cout << dp[j] << endl;
    }
    //cout << i << endl;

    return 0;
}

한시간넘게 매달린 아까꺼의 속편이다. 이번에는 아까처럼 이중for문 돌리면 그냥 시간초과라서 lowerbound를 이용했어야 했다.

새로운 배열 dp를 이렇게 정의 해야 했다. dp[i] = 지금까지 만든 부분배열이 갖는 길이 i 인 증가 부분수열중 최소의 마지막 값

근데 다들 왜 벡터로 하지? 왜 그냥 일반 배열로는 선언을 안할까? 라는 의문을 품는 와중에 시도해본 결과 , 하 ㅅㅂ 분명 풀리긴 할것 같은데 내 머리로는 배열로는 불가다.

[SHEWANTSME]

신해빈 9375

aabcc 같은거는 (2+1) (1+1) (2+1) -1 임. 문제를 풀고 하나씩 적어가다보면 조합이거나 곱셈이겠거니,,, 라는 낌새가 들어야함.

aabcc는 17이 나오는데 어떻게 하면 17을 만들 수 있을까?

a a b c c 이상황에서 (2+2+5+4+4) 암튼 잘 생각해둬야함!! -> 알몸인상태는 빼줘야하니까 -1

#include<iostream>
#include<unordered_map>
#include  <string>
using namespace std;
int n;
int main() {
    cin >> n;
    while (n--) {
        int m; cin >> m;
        int cnt = 1; 
        unordered_map<string, int>mp;
        for (int i = 0; i < m; i++) {
            string s1, s2;
            cin >> s1 >> s2;
            /*if (mp.find(s2) == mp.end())
                mp.insert({ s2,1 });
            else*/ mp[s2]++;
// mp.find를 굳이 안해도 되는게 , 어차피 저 mp[s2]++과정에서 mp.find를 진행하기때문에, 굳이 안써도됨.
        }
        auto ans = 1; // 경우의수는 혹시 모르니까 longlong 형태가 좋대!
        for (auto &ele : mp)
            ans = ans * (ele.second + 1);
        cout << ans - 1 << endl;
    }
    return 0;
}

[SHEWANTSME]

아 그리고 map 은 value로 접근 ㄴㄴ 함.. only with key!!

[SHEWANTSME]

1213번 팰린드롬만들기

-> 문제를 어떻게 구성하느냐가 핵심임!

palindrome의 뭉탱이 {(aaabbb)같은경우는 두개의 뭉텅이} 각각의 원소의 개수가 홀수개인 녀석이 두개가 넘어가면 안됨!

a bbb 이런건 절대 회문이 안되겠지? (홀수개수의 뭉탱이가 2개니깐?)

나머지 경우는 다 됨.

어찌어찌해서 풀긴 했는데 상당히 풀이가 더럽다. 

// 1213번 DONE!! 하 기운빠진다
#include <iostream>
#include <vector>
#include<algorithm>
#include<string>
using namespace std;

int alphabet[26];
int cnt = 0;
int cntidx;
string s, ss,sss;
// 카운팅이 홀수이면서 젤 작은놈이 가운데 와야함
//bbbbbbaaa 이면 a-1, b-3 -> abbb   a   bbba

int main(){
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        alphabet[s[i] - 'A']++;
    }
    for (int i = 0; i < 26; i++) {
        if (alphabet[i] % 2) {  cnt++; cntidx = i;}
                // if(alphabet[i]&1) 이것도 홀수 판별하는거임
// 101->5, 11->3, 1101->13 이런식으루 써도됨
    }
    if (cnt >= 2) { cout << "I'm Sorry Hansoo"; exit(0); }
    else {
        for (int i = 0; i < 26; i++) {
            if (alphabet[i] ) alphabet[i] = alphabet[i] / 2;
        }
        int half = s.size() / 2;
        for (int j = 0; j < 26; j++) {
            while (alphabet[j]) {
                ss.push_back(j + 'A');
                sss = ss;
                alphabet[j]--;
            }
        }
        if (s.size() % 2 == 0) {
            reverse(ss.begin(), ss.end());
            for (int i = 0; i < ss.size(); i++)
                sss.push_back(ss[i]);
        }
        else {
            ss.push_back(cntidx+'A');
            reverse(ss.begin(), ss.end());
            for (int i = 0; i < ss.size(); i++)
                sss.push_back(ss[i]);
        }
        for (int i = 0; i < sss.size(); i++)
            cout << sss[i] << " ";
    }
    return 0;
}
처음 s, 그리고 reverse하느라 쓰이는 ss, sss 때문에 좀 더 더러워보이는건 기분탓
string도 push_back이 된다는 사실!! 은 알게 되었넹 ㅎㅎ

조금 더 깔끔한 선생의 풀이

#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
char str[55], tmp;// 최대 50글자!
vector <char> num;
string s;
int i, j, l, con;
int main() {
    cin >> s;
    sort(s.begin(), s.end());// sort해주자.
    for (i = 0; i < s.size(); i++) {
        if (s[i] == s[i + 1]) {
            num.push_back(s[i]);
            i++;
        }
        else {
            if (!con) {
                tmp = s[i];
                con = 1;
            }
            else con = 2;
        }
    }
    if (con == 2) printf("I'm Sorry Hansoo");
    else {
        for (i = 0; i < num.size(); i++)
            printf("%c", num[i]);
        if (tmp) printf("%c", tmp);
        for (i = num.size() - 1; i >= 0; i--)
            printf("%c", num[i]);
    }
    return 0;
}
so 깔끔 ㅎ
이 풀이가 왜 좋냐면, AAAA 이렇게 짝수 뭉탱이면 0번인덱스 다음 바로 2번인덱스로감(i++이 두개있음
for에 하나, 그 밑에하나) 그래서 짝수 뭉탱이일때는 저렇게 계산하고(짝수라서 가능)
홀수 뭉탱이면 분명 그 다음뭉탱이랑 걸리는게 나오기때문에 con으로 카운팅해주고(2이상이면 아웃)
이런 방식으로 풀면 reverse 할필요도 없고 , string 3개나 만들 필요도 없고, 깔끔히 풀 수 있음

[SHEWANTSME]

유기농 배추 1012

미로찾기보다 생각을 많이 했던 문제임

처음에는 BFS로 지렁이들이 좀비처럼 잠식하는것처럼 코드를 짰지만, 몇몇 경우에서 틀린 값이 나와서

문제를 다시 한번 찬찬히 읽어보니, 그냥 connected component를 구하면 되는 문제였다.

그리고 다시 읽어보니 connected component는 dfs로 빠르게 구할 수 있었다.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int tc, M, N, K, cnt = 0;
int arr[51][51];
int visited[51][51];
int dx[4] = { 0,1,-1,0 };
int dy[4] = { 1,0,0,-1 };
queue<pair<int, int>>q;
// 잠만 근데 뭉텅이 개수 구하려면 dfs필요한거 아닌가?
// DFS로 짜보자..!
void DFS(int a, int b) {
    if(not visited[a][b]) visited[a][b] = 1;
    else return;
    for (int i = 0; i < 4; i++) {
        int nx = a + dx[i];
        int ny = b + dy[i];
        if (nx >= 0 and ny >= 0 and nx < M and ny < N) {
            if (arr[nx][ny] == 1 and not visited[nx][ny]) DFS(nx, ny);
        }
    }
}
int main() {
    cin >> tc;
    while (tc--) {
        cin >> M >> N >> K;
        while (K--) {
            int x, y;
            cin >> x >> y;
            arr[x][y] = 1;
        }
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1 and not visited[i][j]) { cnt++; DFS(i, j); }
            }
        }
        cout << cnt << "\n";
        for (int i = 0; i < M; i++) {
            memset(arr[i], 0, sizeof(int)*N);
            memset(visited[i], 0, sizeof(int)*N); // visited를 초기화 안하면 25퍼에서 틀린다고 나오드라
        }
        cnt = 0;
    }
    return 0;
}

문제 자체는 어렵지 않지만 생각해둬야할게 뭐냐면

이 문제에서는 DFS기준이 , visited를 안했고 + arr[i][j] =1이면 dfs를 도는것이다.

근데 정작 dfs함수안에서는 뭘 하는게 없고

dfs가 돌아가게 해주는 main에서 다시 조건을 걸어야 한다.

if(arr[i][j] == 1 and not visited[i][j])

이렇게 main에서도 다시 걸어줘야

if(arr[i][j] == 1 and not visited[i][j]) { cnt++; DFS(i,j); }

방문했던놈을 다시 방문하지 않고, 그렇게 1의 뭉텅이의 시작을 cnt++해주면 연결된 요소들은

알아서 걸러지기 때문에 효과적으로 count를 할 수 있다.

++ 참고로

   fill(&arr[0][0], &arr[0][0] + 51 * 51, 0);
   fill(&visited[0][0], &visited[0][0] + 51 * 51, 0);

이거는 선생이 푼건데, memset이 0이나 -1초기화할때는 fill보다 빠르니까 그냥 memset쓰셈

for (int i = 0; i < M; i++) {
    memset(arr[i], 0, sizeof(int)*N);
    memset(visited[i], 0, sizeof(int)*N); // sizeof(자료형)*N하면 되지만
 // 4*N 해도됨 ㅋ int의 사이즈는 4, double은 8 , long long 8, char bool은 1 ( 싹다 바이트크기)
}

2차원 배열 초기화 memset은 저렇게 한번 for문 도는 상태에서 해야됨

[SHEWANTSME]

완전히 내힘으로 푼게 아닌 3986 (좋은단어), 1629( 큰수)

한달뒤에 내 힘으로 풀어보자!

(큰 수는 어떤식으로 수를 쪼개면 재귀를 쓰면서 숫자가 작아질 수 있을까? -> 를 생각해보자!!)

[SHEWANTSME]

2468 ( 안전영역)

와 진짜 별거 아니긴 한데, 뭉텅이에서 cnt가 아니라, 뭉텅이별로 cnt하는걸 어떻게 구현할까를 너무 쓰잘데기없이 오랜시간동안 구현생각하느라 골때렸었음.. (사실 진짜 별거아닌데말야)

그래도 존나 골똘히 생각하다가 풀리니까 기분은 좋다.

#include<iostream>
#include<algorithm>
#include<string.h> // for memset
#define endl "\n"
using namespace std;

int arr[101][101]; // 처음 배열
int narr[101][101]; // 1,0으로만 이루어진 배열-> 얘랑 visited만 memset해주면 됨
int visited[101][101];// dfs니깐 당연히 필요
int dx[4] = { 0,1,-1,0 };
int dy[4] = { 1,0,0,-1 };
int num, mx = -1; // 처음배열 사이즈 ,처음배열에서 최댓값
int ct = 0; // 뭉텅이 카운트
int ans = -1; // 최종 답
void DFS(int x, int y) { // DFS자체는 똑같음 
//ct를 여기다 넣어보기도 하고 main에서 삽질도 해봤지만 결국 main에서 하는게 답!
    if (not visited[x][y]) visited[x][y] = 1;
    else return; 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 and ny >= 0 and nx < num and ny < num) {
            if (narr[nx][ny] == 1 and not visited[nx][ny]) DFS(nx, ny);
        }
    }
}

int main() {
    int max = -1; // 이건 물의 level별로 max값을 저장하기위한 변수
    cin >> num;
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            cin >> arr[i][j];
            mx = (mx > arr[i][j]) ? mx : arr[i][j]; // 처음배열의 maximum을 저장하기 위한 mx
        }
    }
    int t = 0; // 처음제출할때 이걸 1로 해서 
// 아니 ㅅㅂ 높이는 1 이상이래매! 해서 빼액댔다가 질문 가보니까
// 비가 아예 안올 경우;; 도 있다해서 0으로 바꾸니까 정답이였음 ㅎ..
    while (t <= mx) {
        for (int i = 0; i < num; i++) 
            for (int j = 0; j < num; j++) 
                if (arr[i][j] - t > 0) narr[i][j] = 1; // 여기서도 삽질이 많았었음..
// 먼저 narr를 싹다 초기화를 한다음에 밑에 애들을 수행해야 되는데 여기에 
// 한꺼번에 하다보니까 에러떳었음.. ( 왜 이런 간단한걸 생각을 안한거지??)

        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                if (narr[i][j] == 1 and not visited[i][j]) DFS(i, j);
                else ct++;// else를 여기다 걸고 ct++를 했어야 했는데
// 자꾸 엄한 if문에다가 ct++하고 else에서 ct=1하고 ct-- 이러니까 틀리지 ㅡ.ㅡ
                max = (max > ct) ? max : ct; // ct의 최댓값을 max
            }
        }
        ans = (ans > (num*num - max)) ? ans : num * num - max; // 최종 답
        for (int i = 0; i < num; i++) { // memset 초기화
            memset(narr[i], 0, sizeof(int)*num);
            memset(visited[i], 0, sizeof(int)*num);
        }
        t++;// 물의 level별로 경우를 체크해야 하니까 t++
        ct = 0;// 물의 level마다 ct를 recheck해야 하니까 0으로 초기화
        max = -1; // max도 초기화
     }
    cout << ans << endl; // 답출력
    return 0;
}

코드 양이 생각보다 긴데, 큰 틀은 유기농 배추랑 비슷함!

다만 , 물이 차오르는것에 따라서 생각을 해줘야한다!!

[SHEWANTSME]

백준 11729 (하노이의 탑)

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll poww(int a, int b) { // 이거는 곱셈 문제에서 나왔던 스킬
    if (b == 1) return a;
    else if (b % 2 == 0) {
        return poww(a, b / 2)*poww(a, b / 2);
    }
    else return poww(a, b - 1)*a;
}

void move_hanoi(int from, int to, int n) {
    cout << from << " " << to << endl;
}
void Sum_hanoi(int from, int to,int sum_number) {
    if (sum_number == 1) {
        move_hanoi(from, to, sum_number);
        return;
    }
    Sum_hanoi(from,6-from-to,sum_number-1);
    move_hanoi(from,to, sum_number);
    Sum_hanoi(6-from-to, to, sum_number - 1);
}

int main() {
    int n; cin >> n;
    cout << poww(2, n) - 1 << endl;
    Sum_hanoi(1,3, n);
    return 0;
}

역시 재귀는 어렵다.. 자세한 내용은 https://github.com/SHEWANTSME/NOVEMBER/issues/1

[SHEWANTSME]

백준 2583 영역 구하기 -> 다시 하기!

DFS활용 문제인데, 뭉텅이의 개수 + 뭉텅이 안에서 카운트 ( 이걸 못해서 며칠동안 고생했다)

하 진짜 왜 이런걸 못하는걸까 ,, ㅜ

#include<iostream>
#include<vector>
#include<algorithm>
#define endl "\n"
using namespace std;
int N, M, C;
int cnt = 0;
int arr[101][101];
bool visit[101][101];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

// DFS 함수 자체는 뭐 똑같다.
void DFS(int x, int y) {
    visit[x][y] = 1;
    cnt++; // DFS안에 들어올때 무조건 cnt를 해준다. 
// DFS로 들어온다는 얘기가 arr는 0일때니깐 그때의 개수들을 파악하면 되니깐
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 and ny >= 0 and nx < N and ny < M) {
            if (arr[nx][ny] == 0 and not visit[nx][ny]) {
                DFS(nx, ny);
            }
        }
    }
}

int main() {
    cin >> N >> M >> C;

    while (C--) {
        int x1, x2, y1, y2;
        cin >> y1 >> x1 >> y2 >> x2;
        for (int i = x1; i < x2; i++) {
            for (int j = y1; j < y2; j++) {
                arr[i][j] = 1; visit[i][j] = 1;
            }
        }
    }
 // 해당 영역만 1로 만들어줌 arr랑 visit 둘다

    vector <int> v;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 0 and not visit[i][j]) {
                cnt = 0;
                DFS(i, j);
                v.push_back(cnt);
            }
        }
    }
    sort(v.begin(), v.end());
    cout << v.size() << endl;
    for (auto &e : v) cout << e << " ";
    return 0;
}

아 참고로 선생은 이렇게 int형 DFS로 풀었음

using namespace std;  
int _map[104][104], m, n, k, x1, x2, y1, y2;
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
vector<int> ret; 
int dfs(int y, int x){
    _map[y][x] = 1; 
    int _ret = 1; 
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i]; 
        int nx = x + dx[i]; 
        if(ny < 0 || ny >= m || nx < 0 || nx >= n || _map[ny][nx] == 1) continue; 
        _ret += dfs(ny, nx); // 이게중요!!!!!!!!!!!
    } 
    return _ret; 
}
int main() { 
    ios_base::sync_with_stdio(false);  
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> m >> n >> k; 
    for(int i = 0; i < k; i++){
        cin >> x1 >> y1 >> x2 >> y2;  
        for(int x = x1; x < x2; x++){
            for(int y = y1; y < y2; y++){
                _map[y][x] = 1; 
            }
        }
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(_map[i][j] != 1) { 
                ret.push_back(dfs(i, j));
            }
        }
    }
    sort(ret.begin(), ret.end());
    cout << ret.size() << "\n";
    for(int _ret : ret) cout << _ret << "\n"; 
    return 0; 
}

[SHEWANTSME]

1926 그림

음.. 뭐 크게 다른건 없다. 중요하게 생각할것은, 퍼져나가고 뭉텅이의 개수와 뭉텅이의 길이를 구할때는 BFS가 훨씬 더 빠르다.

처음에 한게 DFS이고 나중에 한게 BFS이다.

BFS가 훨씬 더 빠른것을 알 수 있다.

기존 BFS에서 아주 살짝 달라진것을 알 수 있다..

#include <iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n, m;
int arr[501][501];
int visited[501][501];
int main() {
    queue<pair<int, int>>q;
    int dx[4] = { 0,1,-1,0 };
    int dy[4] = { 1,0,0,-1 };
    int cnt = 0, cnt2 = 0, mxx = -1;
    int curx, cury;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) 
            cin >> arr[i][j];   

    // using BFS

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++) {
        //  if (visited[i][j] == 0) visited[i][j] = 1;
// 기존처럼 그냥 이런식으로 if를 걸면 안된다. 지금 중요한건 arr[i][j]가 1인 상태에서의 카운트가 중요한건데
// if (visited)만 하면 arr가 1일때의 조건이 빠지게 되기 때문.
            if (visited[i][j] == 0 and arr[i][j] == 1) {
                visited[i][j] = 1; 
                cnt++; // 뭉텅이 개수
            }
            else continue;
            q.push({ i,j });
            cnt2 = 0; // cnt2가 0 으로 초기화가 되어야 뭉텅이별로 길이가 나옴
// 초기화를 안하면 예제대로 하면 4, 6 ,7 16이 됨.. 
// 그래서 초기화를 어디다 시키지 하다가 당연히 while 끝날때쯤에 초기화 하려다가
//안되어서 어차피 한바퀴 돌고 나서 다시 여기로 올때 해줘도 늦지 않겠다 싶어서 여기다 함
            while (not q.empty()) {
                curx = q.front().first;
                cury = q.front().second;
                q.pop();
                cnt2++;
// queue가 pop되고 나서 카운트를 해주는게 심적으로 편함. 
                for (int k = 0; k < 4; k++) {
                    int nx = curx + dx[k];
                    int ny = cury + dy[k];
                    if (nx >= 0 and ny >= 0 and nx < n and ny < m) {
                        if (arr[nx][ny] == 1 and visited[nx][ny] == 0) {
                            visited[nx][ny] = 1;
// 여기서도 해봤는데 전혀 안되더라고
                            q.push({ nx,ny });
                        }
                    }
                }
            } 
//혹시 여기서 cnt2=0 하면 되겟네? 싶어서 보니까 max를 그러면 못구하네?? (무조건 0이랑 비교하는 꼴이니까)
// 그래서 위에서 해준다음, 여기서는 max를 구한거임
            mxx = (mxx > cnt2) ? mxx : cnt2;

        }
}
    cout << cnt << endl; // 뭉텅이 개수
    cout << mxx << endl; // 뭉텅이의 최장 길이
    return 0;
}

하 정말 별거 아닌데 생각이 왜이리 안되었는지.. ㅉㅉ

[SHEWANTSME]

백준 4179 불!

하루 종일 생각하다가 풀린 문제.

굉장히 지저분하게 짰는데, 결론이 되는 알고리즘의 해결방식은 동일함.

불이 퍼질때의 숫자의 상태와 J가 퍼질때의 숫자의 상태를 비교해서

갖가지 반례들을 경우처리하고 ( F랑 j랑 벽으로 나뉘어있을때) 아니면 J의 최솟값의 위치에서 불의 값이 더 크면 ( minJ < F) 이면 탈출가능 , minj가 답 아니면 impossible..

벽을 찾는것도 존나게 귀찮았었다.

// 골똘히 생각했던 4179 불!
// 하 드디어 풀었다 시방바바밤
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int x, y, Jx, Jy, Fx, Fy;
char ch[1001][1001];
int visitedJ[1001][1001];
int visitedF[1001][1001];
int dx[4] = { 0,1,-1,0 };
int dy[4] = { 1,0,0,-1 };
queue<pair<int, int>>vecJ; // 무지성으로 queue를 남발한 경향도 없잖아 있는듯
queue < pair<int, int >> vecF;
queue<pair<int, int>>q2;
queue < pair<int, int >> vecQ;
queue<pair<int, int>>q;
void JBFS(int xx, int yy) {
    while (not q2.empty()) {
        int mx = q2.front().first;
        int my = q2.front().second;
        q2.pop();
        for (int i = 0; i < 4; i++) {
            int nx = mx + dx[i];
            int ny = my + dy[i];
            if (nx >= 0 and ny >= 0 and nx < x and ny < y) {
                if (ch[nx][ny] != '#' and visitedJ[nx][ny] == 0) {
                    visitedJ[nx][ny] = visitedJ[mx][my] + 1;
                    q2.push({ nx,ny });
                }
            }
        }
    }
}

void FBFS(int xx, int yy) {
    while (not q.empty()) {
        int mx = q.front().first;
        int my = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = mx + dx[i];
            int ny = my + dy[i];
            if (nx >= 0 and ny >= 0 and nx < x and ny < y) {
                if (ch[nx][ny] != '#'  and visitedF[nx][ny] == 0) {
                    visitedF[nx][ny] = visitedF[mx][my] + 1;
                    q.push({ nx,ny });
                }
            }
        }
    }
}

int main() {
    cin >> x >> y;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            cin >> ch[i][j];
            if (ch[i][j] == 'J') {
                Jx = i; Jy = j;
                q2.push({ i,j }); // 이게 중요했음! J랑 F가 한개 이상일수도 있어서
                // 애초에 다른queue에 push를 하고 시작했어야함
                visitedJ[i][j] = 1;
            }
            if (ch[i][j] == 'F') {
                Fx = i; Fy = j;
                q.push({ i,j });
                visitedF[i][j] = 1;
            }
        }
    }

    JBFS(Jx, Jy);
    // 벽 찾는 이중 for문,, 존나 머리아프다
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            if (i == 0 and j == 0 and visitedJ[i][j] != 0) vecJ.push({ i,j });
            if (i == 0 and j != 0 and visitedJ[i][j] != 0) vecJ.push({ i,j });
            if (j == 0 and i != 0 and visitedJ[i][j] != 0)vecJ.push({ i,j });
            if (i == x - 1 and j != 0 and visitedJ[i][j] != 0)vecJ.push({ i,j });
            if (j == y - 1 and i != 0 and i != x - 1 and visitedJ[i][j] != 0)vecJ.push({ i,j });
        }
    }

    FBFS(Fx, Fy);
    bool check = false;
    while (!vecJ.empty()) {
        int q = vecJ.front().first;
        int w = vecJ.front().second;
        vecJ.pop();
        vecQ.push({ q,w });
        if (visitedJ[q][w] < visitedF[q][w]) {
            vecF.push({ q,w }); // 불이랑 J랑 그래도 벽안에 같은공간에 있으면 vecF에 push
        }
        if (visitedF[q][w] == 0) check = true;//불이 벽들에게 막혀서 visit도 못한경우
    }

    if (vecF.empty() and check == 0) cout << "IMPOSSIBLE" << endl; // empty+ 벽에 막힌것도 아니면 impossible
    else if (check == 1) {// 벽에 막혔을때
        int minq = 3000;
        int minqx = 0, minqy = 0;
        while (!vecQ.empty()) { // visitedJ의 min이 답
            int q = vecQ.front().first;
            int w = vecQ.front().second;
            vecQ.pop();
            if (minq >= visitedJ[q][w]) {
                minq = visitedJ[q][w];
                minqx = q;
                minqy = w;
            }
        }
        cout << minq << endl;
    }
    else { // 그것도 아니면 아까 vecF에 있는 값으로 똑같은 작업 수행
        int minj = 3000;
        int minjx, minjy;
        while (!vecF.empty()) {
            int q = vecF.front().first;
            int w = vecF.front().second;
            vecF.pop();
            if (minj >= visitedJ[q][w]) {
                minj = visitedJ[q][w];
                minjx = q;
                minjy = w;
            }
        }
        if (minj < visitedF[minjx][minjy]) cout << minj << endl;
    }
    return 0;
}

[SHEWANTSME]

백준 1697 숨바꼭질

일차원배열에서 BFS를 생각해줘야함 나름 counting 배열처럼 생각하면 됨. 범위를 조심하고, dp가 안된다는점 (DAG가 아니고 , cycling 가능성 있어서) 조심하면서 생각하면 됨

아니 근데 왜 자꾸 맞왜틀을 시전하다가

subin 과 brother 사이가 subin이 더 클수도 있고 작을수도 있어서 max , min을 설정해두면 안되었었음.. 그냥 subin이에서 bro까지의 거리만 산출하면 되었던거임

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int arr[200000];
queue<int>q;
int sub, bro, mx = -1, mi, cnt = 0;
void BFS(int person) {
    while (!q.empty()) {
        int a = q.front();

        q.pop();
        if (a < 0) continue;
        if (a == 0) {
            if (a == person) {
                cout << arr[a] - 1 << endl;
                break;
            }
            if (arr[a + 1] == 0) {
                arr[a + 1] = arr[a] + 1;
                q.push(a + 1);
            }
        }
        if (a > 0 and a <= 100000) {
            if (a == person) {
                cout << arr[a] - 1 << endl;
                exit(0);
            }

            if (a + 1 <= 100000 and arr[a + 1] == 0) {
                arr[a + 1] = arr[a] + 1;
                q.push(a + 1);

            }

            if (arr[a - 1] == 0) {
                arr[a - 1] = arr[a] + 1;
                q.push(a - 1);
            }

            if (2 * a <= 100000 and arr[2 * a] == 0) {
                arr[2 * a] = arr[a] + 1;
                q.push(2 * a);
            }

        }
    }
}
int main() {
    cin >> sub >> bro;
    /*mx = (sub > bro) ? sub : bro;
    if (mx == sub) mi = bro;
    else mi = sub;*/
    arr[sub] = 1;
    //arr[mi] = 1;
    q.push(sub);
    BFS(bro);
    return 0;
}

[SHEWANTSME]

1074 Z

이문제 도전한지 꽤 된거같은데 풀렸당.. 내가 푼 방법도 재귀적으로 한것임! ( 다만 조금 더 코딩이 긴것일 뿐)

나는 void으로 한것이고, 다른 사람들은 int 나 ll으로 다른 자료형 쓴 거임.

그리고 생각해보니 배열크기가 arr[2][2]이상 있을 필요가 없더라고.. (개멍청) -> 이거 깨닫는데 수많은 try가 있었음ㅋㅋㅋ

암튼 나의 풀이를 보자면

#include <iostream>
#define ll long long
using namespace std;
//ll arr[16384][16384];
ll arr[2][2];
ll ans = 0;
// 재귀적으로는 어떻게 하지?
void Z(ll na,ll x, ll y) {
    arr[0][0] = 0;  arr[0][1] = 1;  arr[1][0] = 2;  arr[1][1] = 3;
    if (na == 1) {
        ans += arr[x][y];
    }
    if (na >= 2) {
        ll nna = na / 2;
        if (x < na and y < na) {
            Z(nna, x, y);
        }
        if (x < na and y >= na) {
            ll t = na * na;
            ans += t;
            Z(nna, x, y - na);
        }
        if (x >= na and y < na) {
            ll tt = na * na * 2;
            ans += tt;
            Z(nna, x - na, y);
        }
        if (x >= na and y >= na) {
            ll ttt = na * na * 3;
            ans += ttt;
            Z(nna, x - na, y - na);
        }       
    }
}
int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    ll na = (1 << (a - 1)); // 2^(a-1) 승 
    Z(na ,b, c);
    cout << ans << endl;
    return 0;
}

나는 이렇게 void쓰는게 더 편한거같기도 하구..

다른사람들은

#include <iostream>
using namespace std;
int solve(int n, int r, int c){
    if (n == 0) return (0);
    int half = 1 << (n - 1);
    if (r < half && c < half)
        return solve(n - 1, r, c);
    else if (r < half && c >= half)
        return half * half + solve(n - 1, r, c - half);
    else if (r >= half && c < half)
        return half * half * 2 + solve(n - 1 , r - half, c);
    else
        return half * half * 3 + solve(n - 1 , r - half, c - half);
}

int main()
{
    int n, r, c;
    cin >> n >> r >> c;
    cout << solve(n, r, c);
}

근데 이렇게 보니까 존내 깔끔 그 자체네.. ㄷㄷ

[SHEWANTSME]

백준 1011 fly me to the alpha centauri

ㅈ같은 수학문제는 아무리 봐도 ㅈ같다.

ㅈㄴ어렵넹 ,, 겨우 풀기는 했다. 계차수열을 통해서 일반항을 구한다음, 정확히 반띵되는 놈들이라서 다시풀라고하면 못품

#include<iostream>
#include<algorithm>
#define ll long long
#define endl "\n"
using namespace std;
int tc;
ll x, y;
int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> tc;
    while (tc--) {  
        cin >> x >> y;
        if (y - x == 1) cout << 1 << endl;
        else if (y - x == 2) cout << 2 << endl;
        else {
            for (ll i = 2; i < 2147483648; i++) { // 어차피 저기까지 가지도 않음
//n^2-n-1이 수열의 첫항을 구하는 계차수열. an = sigma(n-1)bk 로 구했다.
                if (i*i - i + 1 <= y - x) continue;
                else {// y-x보다 크면
                    if (y - x >= (i - 1)*(i - 1) - (i - 1) + 1 + i - 1) {
// 그 전i 에서의 수열값과 그떄 i의 합이 y-x보다 작거나 같으면 
                        cout << (i - 1) * 2 << endl;
                        // 그전수열의 i값곱하기2
                        break;
                    }
                    else {
                        cout << (i - 1) * 2 - 1 << endl;
                        // 아니면 거기서 1 빼거나
                        break;
                    }
                }
            }
        }
    }
    return 0;
}

잘 읽어보면,, 후으

[SHEWANTSME]

투포인터 RE..

백준 2230번이다.

1. 처음에 틀린풀이

#include<iostream>
#include<algorithm>
#include<vector>
#define endl "\n"
#define ll long long
using namespace std;
ll n, m;
ll arr[100001];
ll minn = 2000000000;
bool check = false;
// two-pointer
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);
    ll left = 0;
    ll right = 0;
    while (left<=right and right <n and left>=0) {
        if (arr[right] - arr[left] < m) {
            right++;
        }
        else if (arr[right] - arr[left] == m) {
            check = true;
            break;
        }
        else {
            minn = arr[right] - arr[left];
            left++;
        }
    }
    if (check == true) cout << m << endl;
    else cout << minn << endl;  
    return 0;
}

위에것이 왜 틀린지 어디서 틀린지 아직도 모르겠다.. 그냥 투포인터 쓸때..

left를 for문돌려서 모든 left의 경우에 따라 안나오는 경우 없게 right을 돌리는게 가장 맘 편한듯.. 이렇게 안하면 정말 보기 힘든 예외처리를 감당할 수가 없다.. ㅅㅂ

결국 맞은 코드

#include<iostream>
#include<algorithm>
#include<vector>
#define endl "\n"
#define ll long long
using namespace std;
ll n, m;
ll arr[100001];
ll minn = 2000000000;
bool check = false;
// two-pointer
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);
    ll left = 0;
    ll right = 0;
    while (left<=right and right <n and left>=0) {
        if (arr[right] - arr[left] < m) {
            right++;
        }
        else {
            if (minn > arr[right] - arr[left]) {
                minn = arr[right] - arr[left];
            }
            left++;
        }
    }
    if (check == true) cout << m ;
    else cout << minn;  
    return 0;
}

맞은코드 2

#include<iostream>
#include<algorithm>
#include<vector>
#define endl "\n"
#define ll long long
using namespace std;
ll n, m;
ll arr[100001];
ll minn = 2000000000;
bool check = false;
// two-pointer
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    arr[n] = 10000000000; // 애초에 n에서 걸리게 arr[n]을 존나큰수로 잡아둠
    ll left = 0;
    ll right = 0;
    sort(arr, arr + n);
    for(int l = 0; l < n ; l++){
        while(arr[right] - arr[l] <m) right++;
        minn = min(minn, arr[right] - arr[l]);
    }
    cout<<minn;
    return 0;
}

근데 위의 풀이는 arr[n]을 어떻게 두냐에 따라 좀 헷갈릴수도 있어서 그냥 맘 편하게 이렇게 하는게 나을듯..

#include<iostream>
#include<algorithm>
#include<vector>
#define endl "\n"
#define ll long long
using namespace std;
ll n, m;
ll arr[100001];
ll minn = 2000000000;
bool check = false;
// two-pointer
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
        ll left = 0;
    ll right = 0;
    sort(arr, arr + n);
    for(int l = 0; l < n ; l++){
        while(right<n and arr[right] - arr[l] <m) right++;
        if( right == n) break;
        minn = min(minn, arr[right] - arr[l]);
    }
    cout<<minn;
    return 0;
}

lowerbound 를 이용한 풀이

--> lower_bound로 해결하려고 하면 하나의 for문으로 처음부터 끝까지 값을 지정하고 그 값에 M을 더한다.

그리고 그 합한 값의 lower_bound를 찾고 그 위치가 배열 내에 있다면 그 위치의 값과 처음에 지정한 값의 차가 M 이상이 될 수 있다는 것이다.

#include<iostream>
#include<algorithm>
#include<vector>
#define endl "\n"
#define ll long long
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
ll n, m;
vector<ll>arr;
int main() {
    fastio; // 앞으로 이렇게 하자 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        ll x; cin >> x; 
        arr.push_back(x);
    }
    sort(arr.begin(), arr.end());
    ll ans = 20000000001;
    for (int i = 0; i < n; i++) { // for문 돌면서
        ll x = arr[i]; // 해당 i 에 대한 값이
        ll value = lower_bound(arr.begin(), arr.end(), x + m) - arr.begin(); // 이부분이 중요한데,
// 지금 형태가 index를 구하는거임. 근데 누구의 인덱스냐면, arr[i]+m의 lowerbound를 구함
        if (value < arr.size()) {
            ans = min(ans, arr[value] - x);
        }
    }
    cout << ans << endl;
    return 0;
}

예를들어 n = 6 , m = 7, arr = {1,2,7,9,11,15} 인 상태면 처음 for문에선 x = 1이고, value는 1+7 = 8의 lowerbound를 구하겠지? -> 지금 arr에 8 이 없으니까 9의 index를 반환(3) 그래서 i==0일때 value =3이고, 3 은 arrsize보다 작으니 ans = arr[3] - arr[0] = 8 그다음 i==1일때 x = 2, value = 3, ans = min(ans, arr[3]-arr[1]) = 7 i==2이면, x=7 , value = 5, ans = min(ans, arr[5]-arr[2]) = 7 .. 이런식으로 쭉 계산함.

백준 부분합 1806번

이것이 정석풀이

#include<iostream>
#include<algorithm>
#include<vector>
#define endl "\n"
#define ll long long
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
ll n, m, sum;
ll minn = 1000000002;
ll arr[100002];
vector<ll>v;
int main(){
    fastio;
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
        cin >> arr[i];
    ll right = 0; // right도 0부터 봐줘야함
    ll sum = arr[0]; // 이거 sum을 arr[0]만 둬야하나 생각했는데 역시 맞았넹
    for(ll left = 0;left <n ; left++){ // left가 인덱스 0부터 도는데
        while(right<n and sum <m){ // sum이 m보다 작을때 while을 도는것이 핵심!
            right++; 
            if(right!=n)sum+=arr[right]; 
        }
        if(right==n)break; // right이 n이면 끝까지 간거니까 minn이 나왔을꺼임 어찌되었든
        minn = min(minn, right-left+1); // 매 경우 min 최신화
        sum-=arr[left]; // sum이 0보다 크니까 여기까지 온거겠지 ( right이 n이면 이미 위에서 걸려짐)
    }
    if(minn != 1000000002) cout << minn<<endl;
    else cout << 0 <<endl;
    return 0;
}

ㅈㄴ게 지저분하고 예외처리 각각 생각해줘야하는 내 풀이

#include<iostream>
#include<algorithm>
#include<vector>
#define endl "\n"
#define ll long long
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
ll n, m, temp, mx;
ll arr[100002];
vector<ll>v;
int main(){
    fastio;
    cin >> n >> m;
    mx = -1;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        mx = (mx > arr[i]) ? mx : arr[i];
    }
    if (mx >= m) { // 젤큰놈이 m보다 크면 생각할 필요가 없음
        cout << 1 << endl;
        exit(0);
    }
    ll right = 1;
    ll left = 0;
    ll sum = arr[0] + arr[1];
    while (left <= right and right < n and left>=0) {
        if (sum < m) {
            right++;
            sum += arr[right];
        }
        else {
            v.push_back(right - left); // 바로 min을 구해도 되는데 그냥 귀차나서 벡터에 때려넣음
            sum -= arr[left];
            left++;
        }
    }
    if(!v.empty()){ // 그냥제출했더니 런타임떠서 보니까 vector에 값 없을수도 있더라고
    sort(v.begin(), v.end());
    cout << v.front()+1 << endl;    
    }   
    else cout <<0<<endl; // 값 없으면 0이겠지 ㅎ
return 0;
}