プログラミングコンテストチャレンジブックっていう本があります。これがけっこう面白くて、具体的な問題を解決する方法を考えるの脳の訓練になります。
解答はC++で書かれているので、それをPythonで書くとどうなるのかを考えながらコツコツやってます。
とりあえず、最初の問題をやってみました。
問題はこんな感じです。
[問題]
数字が書かれたn枚の紙切れが袋に入っています。この袋から紙切れを取り出し、数字を見て袋に戻します。これを４回繰り返して、数字の和がmになっていれば勝ちです。このゲームで、紙切れに書かれている数字がk[1],k[2],k[3]......である時、和がmになり本当に勝てる可能性があるのか調べなさい。勝つ可能性があるならYES、なければNOを出力する。
[制約]
1≦n≦50
1≦m≦10**8
1≦k[i]≦10**8
ということで、書いたのがこれ。この問題解くのに１時間以上かかったよ。
#!/usr/bin/env python
#-*- encoding: utf-8 -*-
m = int(raw_input('the sum: '))
n = int(raw_input('the number of cards: '))
k = [0] * n
for num in range(n):
k[num] = int(raw_input('%s: ' % num))
def check():
for a in range(n):
for b in range(n):
for c in range(n):
for d in range(n):
if k[a] + k[b] + k[c] + k[d] == m:
return 'YES'
f = check()
if not f:
f = 'NO'
print f
４重ループの所で、１つでもマッチした場合に、全てのループを抜ける方法が分からなくて、関数にしてreturnで処理しました。breakだと上の階層のループまで抜けられない。
もっといい書き方があると思うので、どんどんコメントもらえれば嬉しいです。