[Codeforces 1036D] Vasya and Arrays

[Codeforces 1036D] Vasya and Arrays

문제 설명 : 

배열 A와 B가 주어진다. 이 배열에서는 특수한 연산이 정의되어 있는데 그 연산은 배열 내에서 연속한 원소들을 더해서 하나의 원소로 압축할 수 있다. 이 연산을 사용해서 A와 B의 모든 원소들이 일치하도록 만들 수 있는 최대 길이를 구하는 문제이다.

풀이 :

문제의 풀이 자체는 금방 떠올랐다. A배열과 B배열에서 각각 원소들을 차례로 더해나간다. 만약 A의 합 더 크면 B의 원소에서 더하고, B의 합이 더 크면 A의 원소를 더하는 방식으로 A와 B의 합이 같아질 때까지 더해나간다. 그래서 현재 더해야 할 원소의 인덱스를 가리키는 a,b변수가 있다. 이렇게 끝까지 갔을 때, 같아진 적이 총 몇 번인지 세면 된다.

주의할 점 : 

문제의 솔루션자체는 금방 떠올랐다. 구현도 금방 했다. 그런데 데이터를 넣어보니 답이 자꾸 다르게 나왔다. 분명 쉬운 문제인데 자꾸 틀리니 멘탈이 박살났다. 이 문제만 3시간 넘게 붙잡고 있었다. 문제는 while안에서 if문의 분기 처리에 있었다.

while문 안에 분기는 세 가지가 있다. 하나는 A합이 B보다 더 클 때 B의 원소를 더하는 것, B의 합이 더 클 때는 이와 반대로 동작, 마지막으로 A와 B의 합이 같아졌을 때 ans를 1 추가하고 A합과 B합을 다시 갱신하는 것이다. 나는 이 if문들을 else if로 묶지 않고 그냥 if로 묶은 것이 화근이었다. 처음에는 이게 왜 문제가 될까 의아했었는데 실제로는 문제가 생길 수 있다! else로 묶게 되면 if와 else로 묶인 조건문들은 여러 개들 중에서 딱 한 개만 실행된다. 근데 else로 묶지 않아서 if문 조건만 맞는다면 최대 3번까지 모두 실행될 수 있다는 점이다. 나는 이렇게 if로 묶어서 while문을 짜는 것이 총 루프가 적게 돌 것이므로 효율적이라고 판단했는데(실제로 루프가 더 적게 도는 것은 사실이다), 이 경우의 문제점은 a와 b가 한 루프 안에서 여러 번 갱신될 수 있다는 점이다. 여러 번 갱실될 경우 사실 나는 while문에 조건상 a는 n이 되었을 때, b는 m이 되었을 때 종료되도록 의도했었는데, a가 n+1 혹은 b가 m+1이 된 채로 종료될 수도 있다. while문 안에서 a와 b는 딱 한 번씩만 증가하도록 해야한다.

자세한 것은 아래 코드 73~84줄의 while문 내부를 보자.

배운 점 : 

while문 안에서 if문의 else if 분기 처리를 잘못한 것이 이렇게까지 잘못된 결과를 초래할 수 있음을 깨달았다.

코드 :

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/****************************Contest Template******************************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
 
inline void showAll(vector<int> &v,int NL_or_space=0){ //0 is space(default), 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/****************************Contest Template******************************/
const int SIZE= 300009;
 
int A[SIZE],B[SIZE];
 
int main(){
    int n;    scanf("%d",&n);
 
    ll sum=0;
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&A[i]);
        sum=sum+A[i];
    }
 
    int m;    scanf("%d",&m);
 
    for(int i=1 ; i<=m ; i++){
        scanf("%d",&B[i]);
        sum=sum-B[i];
    }
 
    if(sum!=0){
        printf("-1\n");
        return 0;
    }
 
    int ans=0;
    int a=0,b=0;
 
    ll asum=0,bsum=0;
    while(a<n || b<m){
        if(asum<bsum){
            asum+=A[++a];
        }
        else if(asum>bsum){ //if라고 하면 안됨!
            bsum+=B[++b];
        }
        else if(asum==bsum){ //if라고 하면 안됨!
            ans++;
            asum=A[++a],bsum=B[++b];
        }
    }
 
    printf("%d\n",ans);
    return 0;
    
}