AtCoder-ABC221 C - Select Mul【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

AtCoder Beginner Contest221 C - Select Mul

問題文

整数 N が与えられます。N の各桁の数字を取り出して並べ（並べる順序は好きに変えてよい）、2 つの正整数に分離することを考えましょう。

例えば、123 という整数に対しては以下の 6 通りの分離の仕方が考えられます。

・12 と 3
・21 と 3
・13 と 2
・31 と 2
・23 と 1
・32 と 1
なお、ここで分離されたあとの 2 整数に leading zero が含まれていてはなりません。例えば、101 という整数を 1 と 01 の 2 つに分離することはできません。また上述の「正整数に分離する」という条件より、101 を 11 と 0 の 2 つに分離することもできません。

適切に N を分離したとき、分離後の 2 数の積の最大値はいくらになりますか？

制約

・N は 1 以上 10 ^9 以下の整数
・N には 0 でない桁が 2 つ以上含まれる

解答例

n = input()

ans = 0
# bit全探索
for i in range(2**(len(n)-1)):
    tmp1 = []
    tmp2 = []
    # bitに応じてtmp1とtmp2に振り分け
    for j in range(len(n)):
        if (i >> j) & 1:
            tmp1.append(n[j])
        else:
            tmp2.append(n[j])
    # 振り分けされていなければスキップ
    if len(tmp1) == 0 or len(tmp2) == 0:
        continue
    
    # tmp1を最大の値に
    tmp1.sort(reverse=True)
    num1 = ""
    for i in range(len(tmp1)):
        num1 += tmp1[i]
    
    # tmp2を最大の値に
    tmp2.sort(reverse=True)
    num2 = ""
    for j in range(len(tmp2)):
        num2 += tmp2[j]

    # 最大値をメモ
    ans = max(ans,int(num1)*int(num2))

print(ans)