胡瓜のプログラミング日記

ABC079-C Train Ticket(Atcoder精進記録)

C - Train Ticket


Atcoder Beginner Contest 079-C

〇問題
・0以上9以下の4つの整数の間に ’+’ か ’-’ を入れて計算式を作り、その値が 7 になるものを出力。

〇方針
・8通り全部試すほうが早いが、あえてbit探索を使う。

ソースコードC言語

#include <stdio.h>
#include <stdlib.h>

int main(){
    int A[4],i;
    char s[4];
    scanf("%s",s);
    for(i=0;i<4;i++){
        A[i] = s[i] - '0';
    }

    int j,sum;
    char op[3];
    for(i=0;i<8;i++){
        sum = A[0];
        for(j=0;j<3;j++){
            if( i & ( 1 << j ) ){
                op[j] = '+';
                sum += A[j+1];
            }else{
                op[j] = '-';
                sum -= A[j+1];
            }
        }
        if( sum == 7 ){
            break;
        }
    }

    for(i=0;i<3;i++){
        printf("%d%c",A[i],op[i]);
    }
    printf("%d=7\n",A[3]);

    return 0;
}

〇所感
・bit探索は理解したはず。

〇参考記事
AtCoder 版!蟻本 (初級編) (問題の選択)