[코드포스 Practice8] B. 2048 Game

You are playing a variation of game 2048. Initially you have a multiset s of n integers. Every integer in this multiset is a power of two. 당신은 2048 변형 게임을 하고 있다. 처음에 당신은 n개의 정수가 있는 다중집합 s를 가지고 있다. 이 집합에 있는 모든 정수는 2의 제곱이다.

You may perform any number (possibly, zero) operations with this multiset.

당신은 이 집합으로 몇번의 연산을 수행할 수 있다 (0번도 가능)

During each operation you choose two equal integers from s, remove them from s and insert the number equal to their sum into s.

각 연산 동안 당신은 s에 있는 두 개의 정수를 선택해서 s에서 제거하고 두 정수의 합을 s에 넣는다.

For example, if s={1,2,1,1,4,2,2} and you choose integers 2 and 2, then the multiset becomes {1,1,1,4,4,2}.

예를 들어 s가 {1,2,1,1,4,2,2}이고 당신이 정수 2와 2를 선택했다면 s는 {1,1,1,4,4,2}가 된다.

You win if the number 2048 belongs to your multiset. For example, if s={1024,512,512,4} you can win as follows: choose 512 and 512, your multiset turns into {1024,1024,4}. Then choose 1024 and 1024, your multiset turns into {2048,4} and you win.

 

만약 2048이 당신의 집합에 있다면 이긴다. 예를들어 s가 {1024,512,512,4}라면 당신은 이렇게 하면 이길 수 있다: 512, 512를 선택하면 집합이 {1024,1024}가 된다. 다음으로 1024, 1024를 선택하면 집합이 {2048, 4}가 되어 당신이 이긴다.

You have to determine if you can win this game.

당신은 이길 수 있을지를 결정해야한다.

You have to answer q independent queries.

q개의 독립적인 질문에 답해야한다.

Input
The first line contains one integer q (1≤q≤100) – the number of queries.
첫번째 줄은 하나의정수 q를 포함하고 있다 -- 문제의 개수임

The first line of each query contains one integer n (1≤n≤100) — the number of elements in multiset.
각 문제의 첫번째 줄은 하나의 정수 n을 포함하고 있다. -- 집합에 있는 요소의 개수임

The second line of each query contains n integers s1,s2, … ,sn (1≤si≤2^29) — the description of the multiset. It is guaranteed that all elements of the multiset are powers of two.

각 질문의 두번째 줄은 n개의 정수 s1, s2, .. , sn 를 포함하고 있다. -- 집합의 종류임. 집합의 모든 요소가 2의 제곱수임이 보장된다.

Output
For each query print YES if it is possible to obtain the number 2048 in your multiset, and NO otherwise.
2048을 포함하는게 가능하다면 YES를 출력한다. 아니면 NO를 출력한다.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

너가 원하는 어떤 형태로든 모두 출력가능하다 (즉, 예를 들어 문자열 ~~ 도 모두 긍정적인 답으로 인식 될 것이다. )

---

During each operation you choose two equal integers from s, remove them from s and insert the number equal to their sum into s.

 

번역해보니깐 알겠다. 내가 정말 문장을 안 읽고 풀구나..ㅎㅎ 대회 때 이 문장을 안 읽고 풀어서 조금 헤맸음. 같은 두 숫자 선택하는지 몰랐고 그걸 더하는지도 몰랐다. 그냥 곱하다가 나중에 더한다는 걸 깨달았음. 그리고 같은 숫자 선택하는 거였구나ㅋㅋㅋ 그냥 막 선택했다. 

 

 

 

투포인터 조금 헷갈렸음. 시작이랑 끝이 둘 다 0번째인지 아니면 시작은 0, 끝은 1부터 시작하는지... 이거 지칭하는 용어는 뭐였는지.. 그리고 시작이랑 끝 겹치지 않고 항상 끝이 먼저 가있어야 했던 것 같은데 내가 그렇게 짰는지 모르겠다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
 
int main() {
    int q;
    scanf("%d", &q);
    
    for(int i = 0; i < q; i++){
        int n;
        scanf("%d", &n);
        vector<i64> v(n);
        for(int i = 0; i < n; i++){
            scanf("%lld", &v[i]);
        }
        sort(v.begin(), v.end());
        
        i64 count = v[0];
        int s = 0, e = 0;
        for(;;){
            if(s == n-1){
                break;
            }
            if(count > 2048){
                count -= v[s];
                s++;
            }
            else if(count < 2048){
                e++;
                count += v[e];
            }
            else{
                break;
            }
        }
        if(count == 2048){
            printf("YES\n");
            
        }
        else{
            printf("NO\n");
        }
    }
    
    return 0;
}

거의 뭐 야매 투포인터 아니냐

그래도 마 해피뉴이어 봤으면 됐다

 

하지만 찜찜하므로 다시 보는 투포인터

출처 : 북님

아 용어 right랑 left였구나. 게다가 야매 투포인터가 아니라 괜찮게 짠 거 같은데???

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
 
int main() {
    int q;
    scanf("%d", &q);
    
    for(int i = 0; i < q; i++){
        int n;
        scanf("%d", &n);
        vector<i64> v(n);
        for(int i = 0; i < n; i++)
            scanf("%lld", &v[i]);
        sort(v.begin(), v.end());
        
        
        i64 count = v[0];
        int s = 0, e = 0;
        while(s < n){
            if(count > 2048){
                count -= v[s];
                s++;
            }
            else if(count < 2048){
                e++;
                count += v[e];
            }
            else{
                break;
            }
        }
        if(count == 2048)
            printf("YES\n");
        else
            printf("NO\n");
    }
    
    return 0;
}

while 부분만 바꿨다. 만족~~