全探索

問題

$ N $ 個の商品があり、商品 $ i (1 \leqq i \leqq N)$の価格は $ A_i $ 円です。

異なる３つの商品を選び、合計価格をちょうど1000円にすることができるでしょうか。

答えをYesかNoで出力して下さい。

[制約]
🔹$ 3 \leqq n \leqq 100 $

解き方・ソースコード

この問題は３重ループを使うことで解くことができます。

１つめのループは全商品をチェックするために、$ N $ 回実行します。

２つめのループは１つめの商品と同じ商品を選ばないように、$ N - 1 $ 回実行します。

３つめのループは１つめ、２つめの商品と同じ商品を選ばないように、$ N - 2 $ 回実行します。

３重ループの中では、選んだ３つの商品の合計が1000円かどうかを確認します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#--------- 入力例1 ----------
N = 3
A = [200, 300, 400]
#--------- 入力例2 ----------
# N = 5
# A = [100, 200, 300, 400, 500]
#----------------------------
def check(n, a):
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if a[i] + a[j] + a[k] == 1000:
                    return "Yes"
    else:
        return "No"

print(check(N, A))

[実行結果(入力例1)]

No

与えられた３つの価格では1000円になることはないので、解はNoとなります。

[実行結果(入力例2)]

Yes

与えられた５つの価格のうち、[100, 400, 500]を選択すると1000円になりますので、解はYesとなります。