Problem:
 Score : 500 points    Problem Statement We have a chocolate bar partitioned into H horizontal rows and W vertical columns of squares.  The square (i, j) at the i -th row from the top and the j -th column from the left is dark if S_{i,j} is 0 , and white if S_{i,j} is 1 .  We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.  How many times do we need to cut the bar so that every block after the cuts has K or less white squares?      Constraints  1 \leq H \leq 10  1 \leq W \leq 1000  1 \leq K \leq H \times W  S_{i,j} is 0 or 1 .         Input Input is given from Standard Input in the following format:  H  W  K  S_{1,1}S_{1,2}...S_{1,W}  :  S_{H,1}S_{H,2}...S_{H,W}       Output Print the number of minimum times the bar needs to be cut so that every block after the cuts has K or less white squares.        Sample Input 1 3 5 4
11100
10001
00111      Sample Output 1 2  For example, cutting between the 1 -st and 2 -nd rows and between the 3 -rd and 4 -th columns - as shown in the figure to the left - works.  Note that we cannot cut the bar in the ways shown in the two figures to the right.        Sample Input 2 3 5 8
11100
10001
00111      Sample Output 2 0  No cut is needed.       Sample Input 3 4 10 4
1110010010
1000101110
0011101001
1101000111      Sample Output 3 3

Solution (Python):
h, w, k = [int(i) for i in input().split()]
s = [input() for _ in range(h)]

ans = float("inf")
for i in range(2 ** (h - 1)):
    a = 0
    for j in range(h - 1):
        if (i >> j) & 1 == 1:
            a += 1
    c = a
    b = [0] * (c + 1)
    ok2 = True
    for j in range(w):
        tmp = 0
        for l in range(h):
            if s[l][j] == "1":
                b[tmp] += 1
            if (i >> l) & 1 == 1:
                tmp += 1

        ok = True
        for l in b:
            if l > k:
                ok = False

        if not ok:
            a += 1
            b = [0] * (c + 1)

            tmp = 0
            for l in range(h):
                if s[l][j] == "1":
                    b[tmp] += 1
                if (i >> l) & 1 == 1:
                    tmp += 1

            ok = True
            for l in b:
                if l > k:
                    ok = False
            if not ok:
                ok2 = False
                break
    if ok2:
        ans = min(ans, a)

print(ans)

Solution (Python):
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W,K=MI()
    S=[]
    for _ in range(H):
        s=input()
        S.append(s)
        
    
    import itertools
    
    inf=10**10
    ans=inf
    
    import bisect
    for ite in itertools.product([0,1], repeat=H-1):
        temp=sum(ite)
        g=[-1]
        for i in range(len(ite)):
            if ite[i]==1:
                g.append(i)
        
        M=len(g)
        cnt=[0]*M
        
        flag=1
        for j in range(W):
            if flag==0:
                break
            cnt2=[0]*M
            
            
            for i in range(H):
                if S[i][j]=="1":
                    num=bisect.bisect_left(g,i)-1
                    cnt[num]+=1
                    cnt2[num]+=1
            
            
            for i in range(M):
                if cnt2[i]>K:
                    temp=inf
                    flag=0
                    break
                
            
            flag2=0
            for i in range(M):
                if cnt[i]>K:
                    flag2=1
                    break
            
            if flag2:
                for i in range(M):
                    cnt[i]=cnt2[i]
                temp+=1
                
        
                    
        ans=min(ans,temp)
        
    print(ans)
                  
                
                

main()

Solution (Python):

H, W, K = map(int, input().split())
S = [[0]*(W+1) for _ in range(H+1)]
for i in range(1, H+1):
    tmp = list(input())
    for j in range(1, W+1):
        S[i][j] = int(tmp[j-1])


INF = float("inf")
ans = INF

cum = [[0]*(W+1) for _ in range(H+1)]
for i in range(1, H+1):
    for j in range(1, W+1):
        cum[i][j] = cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1] + int(S[i][j] == 1)



for i in range(1<<(H-1)):
    to_cut = []
    tmp = 0
    for j in range(H-1):
        if (i>>j)&1:
            tmp += 1
            to_cut.append(j+1)
    to_cut.append(H)
    blocks = []
    for i in range(len(to_cut)):
        if i == 0:
            blocks.append(cum[to_cut[0]][W])
        else:
            blocks.append(cum[to_cut[i]][W] - cum[to_cut[i-1]][W])
    
    dic = {i: 0 for i in range(1, H+1)}
    ptr = 0
    for i in range(1, H+1):
        if i <= to_cut[ptr]:
            dic[i] = ptr
        else:
            ptr += 1
            dic[i] = ptr
    
    length = len(blocks)
    tmp_sum = [0]*length
    w = 1
    last_cut_pnt = 0
    is_all_bad = 0
    while w <= W:
        for i in range(1, H+1):
            tmp_sum[dic[i]] += int(S[i][w]==1)
        is_over_k = 0
        for i in range(1, H+1):
            if tmp_sum[dic[i]] > K:
                is_over_k = 1
                break
        
        if is_over_k:
            tmp_sum = [0]*length
            tmp += 1
            if last_cut_pnt == w:
                is_all_bad = 1
                break
            last_cut_pnt = w
        else:
            w += 1

    if is_all_bad:
        continue
    else:
        ans = min(ans, tmp)

print(ans)

Solution (Python):
H, W, K = map(int, input().split())
Ss = [list(map(int, input().replace("\n", ""))) for _ in range(H)]

cut_yoko_patterns = ["0","1"]
options = ["0","1"]

import copy

for i in range(H-2):
    cut_yoko_patterns = [cut_yoko_patterns[i] + options[j] for i in range(len(cut_yoko_patterns)) for j in range(len(options))]

answer = int(1e+5)
for cut_yoko_pattern in cut_yoko_patterns:
    yoko_cut_num = cut_yoko_pattern.count("1")
    boxs = [0 for _ in range(yoko_cut_num+1)]
    box_num = [0 for _ in range(H)]
    for i in range(H-1):
        if cut_yoko_pattern[i] == "1":
            box_num[i+1] = box_num[i] + 1
        else:
            box_num[i+1] = box_num[i]
    
    tate_cut_num = 0
    for j in range(W):
        temp_boxs = [0 for _ in range(yoko_cut_num+1)]
        for i in range(H):
            if Ss[i][j] == 1:
                temp_boxs[box_num[i]] += 1
        Impossible = False
        Should_cut = False
        for i in range(yoko_cut_num+1):
            if temp_boxs[i] > K:
                Impossible = True
            
            elif boxs[i] + temp_boxs[i] > K:
                Should_cut = True
        
        if Impossible == True:
            break
        elif Should_cut ==True:
            boxs = copy.deepcopy(temp_boxs)
            tate_cut_num += 1
        else:
            for i in range(yoko_cut_num+1):
                boxs[i] += temp_boxs[i]
    else:
        
        if tate_cut_num+yoko_cut_num < answer:
            answer = tate_cut_num + yoko_cut_num
print(answer)

Solution (Python):
h,w,k=map(int,input().split())
cho=[]
for _ in range(h):
    a=list(input())
    for f in range(w):
      a[f]=int(a[f])
    cho.append(a)

ans=1000000000009

for i in range(2**(h-1)):
    cut=0
    cut_n=[]
    b=[]
    for j in range(h-1):
        if (i>>j)&1:
            cut_n.append(j+1)
            cut+=1
    if len(cut_n)==0:
        ok=1
        dp=0
        for i in range(w):
            wa=0
            for j in range(h):
                wa+=cho[j][i]

            if dp+wa>k:
                cut+=1
                dp=wa
            else:
              dp+=wa

            if wa>k:
                ok+=1
                break
            
        if ok==1:
          ans=min(ans,cut)

    else:
        st=0
        for t in range(len(cut_n)):
            if t==len(cut_n)-1:
                b.append(cut_n[t]-st)
                b.append(h-cut_n[t])
            else:
              b.append(cut_n[t]-st)
              st=cut_n[t]
        
        dp=[0 for _ in range(len(b))]
        ok=1
        for y in range(w):
            for g in dp:
                if g>k:
                    ok+=1
                    break
            st=0
            ch=0
            c=[]
            for e in range(len(b)):
              p=b[e]
              temp=0
              for q in range(p):
                  temp+=cho[st+q][y]
                    
                  dp[e]+=cho[st+q][y]

              c.append(temp)
                
              st+=p

            for g in dp:
                if g>k:
                    ch+=1

            if ch!=0:
                cut+=1
                dp=c

            
            for last in c:
                  if last>k:
                      ok+=1

        
        if ok==1:
            ans=min(ans,cut)

print(ans)

Solution (Python):
H, W, K = map(int, input().split())
HW = [[0] * W for i in range(H)]
S = [0] * H
for i in range(H):
  x = str(input())
  for j in range(len(x)):
    HW[i][j] = int(x[j])


for i in range(H):
  S[i] = sum(HW[i])


ans = H + W
for i in range(2 ** (H - 1)):
  time = 0
  now = 0
  cut = []
  for j in range(H - 1):
    if (i >> j) & 1:
      cut.append(j)
  
  cut2 = [[] for _ in range(len(cut) + 1)]
  for j in range(len(cut)):
    for p in range(now, cut[j] + 1):
      cut2[j].append(p)
      now = cut[j] + 1
  for p in range(now, H):
    cut2[-1].append(p)
  
    
  time = len(cut2) - 1  
  choco = [0] * len(cut2)
  for l in range(W):
    for k in range(len(cut2)):
      nn = 0
      for p in cut2[k]:
        nn += HW[p][l]
      if nn > K:  
        time += 10000
      else:
        choco[k] += nn
      

    if max(choco) > K: 
      time += 1
      for k in range(len(cut2)):
        nn = 0
        for p in cut2[k]:
          nn += HW[p][l]
        choco[k] = nn  

  ans = min(ans, time)
  
  
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
acc = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
    for j in range(1, W + 1):
        acc[i][j] = acc[i][j - 1] + int(S[i][j - 1])


ans = INF
for bit in range(1 << (H - 1)):
    base = 0
    vertical = []
    for i in range(H - 1):
        if bit & 1 << i > 0:
            vertical.append((base, i))
            base = i + 1
    vertical.append((base, H - 1))

    tmp_ans = len(vertical) - 1
    prev = 0
    j = 1
    valid = False
    while j <= W:
        ok = True
        for v in vertical:
            now = 0
            for i in range(v[0], v[1] + 1):
                now += acc[i][j] - acc[i][prev]
            if now > K:
                ok = False
        if ok:
            valid = True
        else:
            if valid:
                prev = j - 1
                tmp_ans += 1
                valid = False
                continue
            else:
                break
        j += 1
    if valid:
        ans = min(tmp_ans, ans)
print(ans)

Solution (Python):
H,W,K=map(int,input().split())
S=[[int(s) for s in input()] for i in range(H)]

ans=1000000
for i in range(2**(H-1)):
    tmp=0
    L=[]
    for j in range(H-1):
        if i>>j&1:
            L.append(j)
    tmp+=len(L)
    L.append(H-1)
    c=[0]*len(L)
    for k in range(W):
        h=0
        c1=[0]*len(L)
        for l in range(len(L)):
            for m in range(h,L[l]+1):
                c1[l]+=S[m][k]
            h=L[l]+1
        p=0
        for l in range(len(L)):
            if c1[l]>K:
                p=2
                break
            elif c[l]+c1[l]>K:
                p=1
            else:
                c[l]+=c1[l]
        if p==2:
            break
        elif p==1:
            c=[i for i in c1]
            tmp+=1
    else:
        ans=min(ans,tmp)
print(ans)

Solution (Python):








def solve(H, W, K, Si):
    Si = [[int(i) for i in S] for S in Si]
    ans = H + W
    for i in range(2 ** (H - 1)):
        h_border = bin(i).count('1')
        w_border = 0
        white_counts = [0] * (h_border + 1)
        choco_w = 0
        for w in range(W):
            choco_w += 1
            wc_num = 0
            tmp_count = [0] * (h_border + 1)
            for h in range(H):
                white_counts[wc_num] += Si[h][w]
                tmp_count[wc_num] += Si[h][w]
                if i >> h & 1:
                    wc_num += 1
            if max(white_counts) > K:
                if choco_w == 1:
                    break  
                w_border += 1
                white_counts = tmp_count
                choco_w = 1
        else:
            ans = min(ans, h_border + w_border)
    print(ans)


if __name__ == '__main__':
    H, W, K = map(int, input().split())
    Si = [input() for _ in range(H)]
    solve(H, W, K, Si)

Solution (Python):
import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def search(topx, topy, botx, boty, grid):
    ret = grid[boty][botx]
    if topx > 0: ret -= grid[boty][topx - 1]
    if topy > 0: ret -= grid[topy - 1][botx]
    if topx > 0 and topy > 0: ret += grid[topy - 1][topx - 1]
    return ret

def Main():
    H, W, K = read_ints()
    chocolate = [list(read_str()) for _ in range(H)]
    
    grid = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if chocolate[h][w] == '1': grid[h][w] += 1
            if w > 0: grid[h][w] += grid[h][w - 1]
            if h > 0: grid[h][w] += grid[h - 1][w]
            if h > 0 and w > 0: grid[h][w] -= grid[h - 1][w - 1]

    ans = INF
    for bit in range(1 << ~-H):
        cnt = 0
        cut = []
        for h in range(~-H):
            if bit >> h & 1:
                cnt += 1
                cut.append(h)
        cut.append(~-H)

        white = [0] * len(cut)
        topx = 0
        flag = False
        for w in range(~-W):
            topy = 0
            for i in range(len(cut)):
                if search(topx, topy, w, cut[i], grid) > K:
                    flag = True
                    break
                white[i] = search(topx, topy, w+1, cut[i], grid)
                topy = cut[i] + 1
            if flag: break
            for x in white:
                if x <= K:
                    continue
                topx = w + 1
                cnt += 1
                break
        if not flag:
            ans = min(ans, cnt)
    print(ans)
    

if __name__ == '__main__':
    Main()

Solution (Python):
import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def search(topx, topy, botx, boty, grid):
    ret = grid[boty][botx]
    if topx > 0: ret -= grid[boty][topx - 1]
    if topy > 0: ret -= grid[topy - 1][botx]
    if topx > 0 and topy > 0: ret += grid[topy - 1][topx - 1]
    return ret

def Main():
    H, W, K = read_ints()
    chocolate = [list(read_str()) for _ in range(H)]
    
    grid = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if chocolate[h][w] == '1': grid[h][w] += 1
            if w > 0: grid[h][w] += grid[h][w - 1]
            if h > 0: grid[h][w] += grid[h - 1][w]
            if h > 0 and w > 0: grid[h][w] -= grid[h - 1][w - 1]

    ans = INF
    for bit in range(1 << ~-H):
        cnt = 0
        cut = []
        for h in range(~-H):
            if bit >> h & 1:
                cnt += 1
                cut.append(h)
        cut.append(~-H)

        white = [0] * len(cut)
        topx = 0
        flag = False
        for w in range(~-W):
            topy = 0
            for i in range(len(cut)):
                if search(topx, topy, w, cut[i], grid) > K:
                    flag = True
                    break
                white[i] = search(topx, topy, w+1, cut[i], grid)
                topy = cut[i] + 1
            if flag: break
            for x in white:
                if x <= K:
                    continue
                topx = w + 1
                cnt += 1
                break
        if not flag:
            ans = min(ans, cnt)
    print(ans)
    

if __name__ == '__main__':
    Main()

Solution (Python):
h,w,kk = map(int,input().split())
s = [list(map(int, input())) for i in range(h)]

ans = h+w-2
for i in range(1 << (h-1)):
    tate = 0
    index = [0] * h
    
    for j in range(h-1):
        if i & (1 << j):
            tate += 1
        index[j+1] = tate 
    chocos = [0]*(tate + 1) 
    yoko = 0
    ok = True
    for j in range(w):
        for k in range(h):
            chocos[index[k]] += s[k][j]
            
        if max(chocos) > kk:
            yoko += 1
            chocos = [0]*(tate+1)
            for l in range(h):
                chocos[index[l]] += s[l][j]
            if max(chocos) > kk:
                ok = False
        if not ok:
            break
    if ok:
        ans = min(ans, tate + yoko)

print(ans)

Solution (Python):
H, W, K = map(int, input().split())

S = [list(map(int, input())) for _ in range(H)]

C = [[0 for w in range(W)] for h in range(H)] 


for h in range(H):
  for w in range(W):
    
    C[h][w] = C[h][w-1] + S[h][w]


def settify(l):
  set_label = set()
  i = 0
  while l > 0:
    if l % 2 == 1:
      set_label.add(i)
    l //= 2
    i += 1
  return set_label
    
def set_label(s):
  tmp = 0
  for i in s:
    tmp += 2**i
  return tmp

def sum_set(s, w):
  s_list = list(s)
  s_list.sort()
  s_list.append(H-1)
  tmp = 0
  it = 0
  ans_list = []
  for h in range(H):
    tmp += C[h][w]
    
    if h == s_list[it]:
      ans_list.append(tmp)
      tmp = 0
      it += 1
  return ans_list    

ans = 10**8
for l in range(2**(H-1)):
  s = settify(l)
  lt_prv = [0 for _ in range(len(s)+1)]
  lt_now = [0 for _ in range(len(s)+1)]
  lt_1minus = [0 for _ in range(len(s)+1)]
  tmp = len(s)
  w = 0
  w_prv = -1
  imp = False
  while w < W:
    lt_now = sum_set(s, w)
    flag = False
    for j in range(len(s)+1):
      if lt_now[j] - lt_prv[j] > K:
        flag = True
        break
    if flag:
      if w_prv == w-1:
        imp = True
      tmp += 1
      lt_prv = lt_1minus
      w_prv = w-1
    w += 1
    lt_1minus = lt_now
    if imp:
      break
    
    
  if not imp:
    ans = min(ans, tmp)
      
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
S = [list(input()) for _ in range(H)]

res = float('inf')
for i in range(2**(H-1)):
    c = bin(i).count('1')
    cnt = c
    sum_l = [0] * (c+1)
    j = 0
    flag = True
    while j < W:
        tmp = sum_l.copy()
        pos = 0
        for k in range(H):
            if S[k][j] == '1':
                tmp[pos] += 1
            if (i >> k) & 1:
                pos += 1
        if max(tmp) <= K:
            sum_l = tmp.copy()
            j += 1
            flag = False
        else:
            if flag:
                cnt = float('inf')
                break
            cnt += 1
            flag = True
            sum_l = [0] * (c+1)

    res = min(res, cnt)

print(res)

Solution (Python):



h, w, k = map(int, input().split())
a = [list(map(int, list(input()))) for _ in range(h)]

ret = 100000
for i in range(2 ** (h-1)):
    hi = [0] * h
    for j in range(h-1):
        hi[j+1] += hi[j] + (i >> j & 1)
    cnt = max(hi)
    pj = 0
    x = []
    while pj < w:
        s = [0] * 10
        fg = False
        for j in range(pj, w):
            for t in range(h):
                s[hi[t]] += a[t][j]
            if max(s)>k:
                if j == pj:
                    cnt = 100000
                    fg = True
                    break
                else:
                    x.append(j)
                    cnt += 1
                    pj = j
                break
            if j == w-1:
                pj = w
                break
        if fg:
            break
    ret = min(ret, cnt)
print(ret)

Solution (Python):
h,w,k=map(int,input().split())
S=[input() for i in range(h)]

LIS=[]

def saiki(x,st):
    if x==h-1:
        LIS.append(st)
        return
    else:
        saiki(x+1,st+st[-1])
        saiki(x+1,st+str(int(st[-1])+1))

saiki(0,"0")

DIC1={c:0 for c in "0123456789"}
DIC2={c:0 for c in "0123456789"}
ans=10**9
for cod in LIS:
    for ele in DIC1:
        DIC1[ele]=0
    cnt=int(cod[-1])
    end=False
    for i in range(w):
        for ele in DIC2:
            DIC2[ele]=0
        for q in range(h):
            if S[q][i]=="1":
                DIC2[cod[q]]+=1
        if max(DIC2.values())>k:
            end=True
            break
        flg=True
        for ele in DIC1:
            if DIC1[ele]+DIC2[ele]>k:
                flg=False
                break
        if flg:
            for ele in DIC1:
                DIC1[ele]+=DIC2[ele]
        else:
            for ele in DIC1:
                DIC1[ele]=DIC2[ele]
            cnt+=1
    if end:
        continue
    ans=min(ans,cnt)
    
print(ans)

Solution (Python):
from itertools import product

H, W, K = map(int, input().split())
grid = ""

for _ in range(H):
  grid += input()

ans = 10000

for Hcut in product((0, 1), repeat = H-1):
  Gr_num = sum(Hcut) + 1
  old = [0]*Gr_num
  cnt = 0
  for i in range(W):
    
    choco = grid[i::W]
    new = [0]*Gr_num
    gr = 0
    for j in range(H):
      new[gr] += int(choco[j])
      if j < H-1:
        if Hcut[j] == 1:
          gr += 1
    
    if max(new) > K:
      cnt += 10000
      break
    
    check = [old[gr] + new[gr] for gr in range(Gr_num)]
    if max(check) > K:
      old = new[:]
      cnt += 1
    else:
      old = check[:]
  ans = min(ans, cnt+sum(Hcut))

print(ans)

Solution (Python):
"""
Hが少ないので、縦で割るパターンは全探索して見る。
dpとか使わずに、貪欲的に割っていけばよい。

"""
H,W,K = map(int,input().split())
choco = [list(input()) for _ in range(H)]
accum = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        accum[i][j] = accum[i][j-1] + int(choco[i][j])

ans = float("INF")
for i in range(2**H):
    """
    i を2進数表記したときに1になっているインデックスに該当する行数で分割する。
    例えば00100なら3行目と4行目の間で分割する。
    """
    binI = format(i,"0"+str(H)+"b")
    group = {}
    groupNum = 0
    for j in range(H):
        group[j] = groupNum
        if binI[j] == "1":
            groupNum += 1
    breakCnt = groupNum
    tmp = [0]*(groupNum+1)
    for j in range(W):
        tmp2 = [0]*(groupNum+1)
        for k in range(H):
            groupNum = group[k]
            if choco[k][j] == "1":
                tmp2[groupNum] += 1
        if max(tmp2) > K:
            break
        else:
            for l in range(groupNum+1):
                tmp[l] += tmp2[l]
            if max(tmp) > K:
                breakCnt += 1
                tmp = tmp2
    else:
        ans = min(ans,breakCnt)
print(ans)

Solution (Python):
import itertools
H, W, K = map(int, input().split())
grid = []
for _ in range(H):
    line = list(input())
    grid.append(line)



ans = 10**9


for ptn in itertools.product([0, 1], repeat=H - 1):

    
    able = True
    for w in range(W):
        
        lines = [0] * (sum(ptn) + 1)
        
        line_num = 0
        for h in range(H):
            
            if grid[h][w] == "1":
                lines[line_num] += 1

            
            
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        
        if max(lines) > K:
            able = False
            break
    if able == False:
        continue
    

    
    lines = [0] * (sum(ptn) + 1)
    
    cnt = sum(ptn)
    
    
    w = 0
    while w < W:
        line_num = 0
        for h in range(H):
            
            if grid[h][w] == "1":
                lines[line_num] += 1
            
            
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        
        
        if max(lines) > K:
            cnt += 1
            lines = [0] * (sum(ptn) + 1)
            w -= 1
        w += 1
    ans = min(ans, cnt)

print(ans)

Solution (Python):
import itertools
H, W, K = map(int, input().split())
grid = []
for _ in range(H):
    line = list(input())
    grid.append(line)



ans = 10**9


for ptn in itertools.product([0, 1], repeat=H - 1):

    
    able = True
    for w in range(W):
        
        lines = [0] * (sum(ptn) + 1)
        
        line_num = 0
        for h in range(H):
            
            if grid[h][w] == "1":
                lines[line_num] += 1

            
            
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        
        if max(lines) > K:
            able = False
            break
    if able == False:
        continue
    

    
    lines = [0] * (sum(ptn) + 1)
    
    cnt = sum(ptn)
    
    
    w = 0
    while w < W:
        line_num = 0
        for h in range(H):
            
            if grid[h][w] == "1":
                lines[line_num] += 1
            
            
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        
        
        if max(lines) > K:
            cnt += 1
            lines = [0] * (sum(ptn) + 1)
            w -= 1
        w += 1
    ans = min(ans, cnt)

print(ans)

Solution (Python):
import itertools
H, W, K = map(int, input().split())
grid = []
for _ in range(H):
    line = list(input())
    grid.append(line)



ans = 10**9


for ptn in itertools.product([0, 1], repeat=H - 1):

    
    able = True
    for w in range(W):
        
        lines = [0] * (sum(ptn) + 1)
        
        line_num = 0
        for h in range(H):
            
            if grid[h][w] == "1":
                lines[line_num] += 1

            
            
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        
        if max(lines) > K:
            able = False
            break
    if able == False:
        continue
    

    lines = [0] * (sum(ptn) + 1)
    cnt = sum(ptn)
    w = 0
    while w < W:
        line_num = 0
        for h in range(H):
            if grid[h][w] == "1":
                lines[line_num] += 1
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        
        if max(lines) > K:
            cnt += 1
            lines = [0] * (sum(ptn) + 1)
            w -= 1
        w += 1
    ans = min(ans, cnt)

print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def bit_search(n):
    res = []
    for i in range(2**n):
        st = set()
        for j in range(n): 
            if ((i >> j) & 1):
                st.add(j)
        res.append(st)
    return res

def main():
    H,W,K=mi()
    
    G = []
    for i in range(H):
        G.append(list(input()))
    
    v = [[0] * W for _ in range(H+1)]
    for w in range(W):
        for h in range(H):
            white_choc = G[h][w] == "1"
            v[h+1][w] = v[h][w] + white_choc
    
    ans = INF
    for borders in bit_search(H):
        counts = [[0] for _ in range(20)]
        k_fact = 1
        W_borders = []

        failed = False
        from_zero = True
        w = 0
        while w < W:
            pre = 0
            over_K = False

            max_diff = 0
            for i,border in enumerate(borders):
                if border == 0: continue
                count = v[border][w] - v[pre][w]
                if not from_zero:
                    count += counts[i][-1]
                else:
                    if count > K:
                        failed = True
                        break
                
                if count > K:
                    over_K = True
                

                counts[i].append(count)
                pre = border
            
            count = v[H][w] - v[pre][w]
            if not from_zero:
                count += counts[i+1][-1]
            else:
                if count > K:
                    failed = True
                    break

    
            if count > K:
                over_K = True


            counts[i+1].append(count)
            if over_K:
                W_borders.append(w-1)
                from_zero = True

                for c in counts:
                    if len(c) == 0: continue
                    c.pop() 
            else:
                from_zero = False
                w += 1

            
            if failed:
                break

        
        if not failed:
            
            
            
            
            
            count_of_ope = len(borders) + len(W_borders)
            ans = min(count_of_ope,ans)


    print(ans)




if __name__ == "__main__":
    main()

Solution (Python):
from itertools import product
import copy
H,W,K = list(map(int, input().split()))
A = []
for i in range(H):
  A.append(list(map(int, input())))



ANS = []
for pat in product(['0','1'], repeat = H-1):
  res = []
  cnt = 0
  now = copy.copy(A[0])
  for i in range(1,H):
    p = pat[i-1]
    if p == '1':
      res.append(now)
      now = copy.copy(A[i])
      cnt += 1
    else:
      for j in range(W):
        now[j] += A[i][j]
  res.append(now)
  
  """  
  print("---")
  print(pat)
  print(res)
  print(cnt)
  """  
  wk2 = [0] * len(res)
  cnt2 = 0
  flg = True
  for x in range(W):
    for j in range(len(res)):
      if res[j][x] > K:
        
        flg = False
        break
      if wk2[j] + res[j][x] > K:
        cnt2 += 1
        wk2 = [0] * len(res)
        break
    for j in range(len(res)):
      wk2[j] += res[j][x]
    if not flg:
      break
      
  if flg:
    ANS.append(cnt + cnt2)
    
print(min(ANS))