Coding 공부

def Innerbound(x,y):
    if 0<=x<N and 0<=y<M:
        return True
    else:
        return False

def dfs(idx,bit,total):
    global result
    if bit == 2**(N*M)-1:
        result = max(result,total)
        return
    else:
        if 2**idx&bit:
            dfs(idx+1,bit,total)
        else:
            x,y = idx//M, idx%M
            nx,ny = x,y
            temp_bit = bit
            temp_num = 0
            while Innerbound(nx,ny):
                if visited[nx][ny]:
                    next_idx = nx*M + ny
                    visited[nx][ny] = False
                    temp_bit = temp_bit|(2**next_idx)
                    temp_num = temp_num*10 + arr[nx][ny]
                    nx = nx + 1
                    ny = ny
                else:
                    break
            for rx in range(nx-1,x-1,-1):
                dfs(idx+1,temp_bit,total + temp_num)
                temp_num = temp_num//10
                next_idx = rx*M + y
                temp_bit = temp_bit^(2**next_idx)
                visited[rx][y] = True
            nx,ny = x,y
            temp_bit = bit
            temp_num = 0
            while Innerbound(nx,ny):
                if visited[nx][ny]:
                    next_idx = nx*M + ny
                    visited[nx][ny] = False
                    temp_bit = temp_bit|(2**next_idx)
                    temp_num = temp_num*10 + arr[nx][ny]
                    nx = nx
                    ny = ny + 1
                else:
                    break
            for ry in range(ny-1,y-1,-1):
                dfs(idx+1,temp_bit,total + temp_num)
                temp_num = temp_num//10
                next_idx = x*M + ry
                temp_bit = temp_bit^(2**next_idx)
                visited[x][ry] = True


N,M = map(int,input().split())

arr = [list(map(int,list(input()))) for _ in range(N)]

visited = [[True for _ in range(M)] for _ in range(N)]
result = 0
dfs(0,0,0)
print(result)

처음에 모든 경우들을 각각 하나씩 그려보면서 dfs를 해주었다.

가로 혹은 세로로 최대한 세울 수 있는 직사각형을 그려주고 그때부터 dfs를 하고 하나씩 내려주면서 dfs를 해주었다.

이 방식은 오래걸리는 방식이였고, 다른 사람들의 풀이를 보고 다시 푼 방식은 다음과 같다.

N,M = map(int,input().split())

arr = [list(map(int,list(input()))) for _ in range(N)]
result = 0
# 0은 가로인걸로 1은 세로인걸로 판별
for bit_shape in range(2**(N*M)):
    total_sum = 0
    for x in range(N):
        sub_sum = 0 # 작은 단위의 SUM
        for y in range(M):
            idx = x*M + y
            if not bit_shape & (1<<idx):
                sub_sum = sub_sum*10 + arr[x][y]
            else:
                total_sum += sub_sum
                sub_sum = 0
        total_sum += sub_sum
    
    for y in range(M):
        sub_sum = 0
        for x in range(N):
            idx = x*M + y
            if bit_shape & (1<<idx):
                sub_sum = sub_sum*10 + arr[x][y]
            else:
                total_sum += sub_sum
                sub_sum = 0
        total_sum += sub_sum
    result = max(result,total_sum)
print(result)

이 방식은 모든 경우를 먼저 구하는 거다. 이 문제는 최대 16개의 칸을 가지는 것이다.

이것을 비트로 표현해서 0이면 가로로 그려진 직사각형 1이면 세로인 직사각형으로 구분을 해주는것이다.

그러면 우리는 2**(N*M)의 경우의 수를 가질수 있다. 최대 65536가지이므로, 빠르게 구할 수 있다.

비트로 현재 종이조각의 상태를 구분하고, 그 상태에 맞게 숫자를 세서 최대값을 구하면 된다.

import sys
from itertools import combinations
def input():
    return sys.stdin.readline().rstrip()


N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]
row = [sum(i) for i in arr]
col = [sum(i) for i in zip(*arr)]
new_arr = [i+ j for i, j in zip(row, col)]
total_sum = sum(new_arr)//2
result = float('inf')
for num in range(1,N//2+1):
    for combi in combinations(new_arr,num):
        result = min(result,abs(total_sum-sum(combi)))
        if result == 0:
            break
    if result == 0:
        break
print(result)

이 문제는 과거에 푼 boj.kr/14889 이 있었기 때문에 빨리 풀 수 있었다. 

기본 푼 방식은 원래와 똑같다. 각 col,row의 섬을 미리 구해놓고, 그걸 통해서 문제를 푸는 방식이다.

from itertools import permutations

import sys
input = sys.stdin.readline
def rotate(command,moving_arr):
    global arr
    cnt = 1
    while cnt<=command[2]:
        start_row,start_col = command[0]-cnt, command[1]-cnt
        end_row,end_col = command[0] + cnt,command[1] + cnt
        for row in range(start_row,end_row+1):
            if row == start_row or row == end_row:
                if row == start_row:
                    for col in range(start_col,end_col+1):
                        if col == end_col:
                            moving_arr[row+1][col] = prev_arr[row][col]
                        else:
                            moving_arr[row][col+1] = prev_arr[row][col]
                else:
                    for col in range(end_col,start_col-1,-1):
                        if col == start_col:
                            moving_arr[row-1][col] = prev_arr[row][col]
                        else:
                            moving_arr[row][col-1] = prev_arr[row][col]
            else:
                moving_arr[row-1][start_col] = prev_arr[row][start_col]
                moving_arr[row+1][end_col] = prev_arr[row][end_col]
        cnt += 1


N,M,K = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
command_list = []
for _ in range(K):
    x,y,r = map(int,input().split())
    command_list.append((x-1,y-1,r))
result = float('inf')

for commands in permutations(command_list):
    move_arr = [row[:] for row in arr]
    prev_arr = [row[:] for row in arr]
    for command in commands:
        rotate(command,move_arr)
        prev_arr = [row[:] for row in move_arr]
    arr_min = min(list(map(sum,move_arr)))
    result = min(arr_min,result)
print(result)

from itertools import permutations

import sys
input = sys.stdin.readline


def rotate(command,move_arr):
    x,y,s = command
    for i in range(1,s+1):
        subtract_data = move_arr[x-i][y-i] # 좌측 최상단 꼭지점을 빼놓기
        for r in range(x-i,x+i): # 좌측 세로를 아래에서 위로 올리는 과정
            move_arr[r][y-i] = move_arr[r+1][y-i]
        for c in range(y-i,y+i):
            move_arr[x+i][c] = move_arr[x+i][c+1]
        for r in range(x+i,x-i,-1):
            move_arr[r][y+i] = move_arr[r-1][y+i]
        for c in range(y+i,y-i+1,-1):
            move_arr[x-i][c] = move_arr[x-i][c-1]
        move_arr[x-i][y-i+1] = subtract_data
        





N,M,K = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
command_list = []
for _ in range(K):
    x,y,r = map(int,input().split())
    command_list.append((x-1,y-1,r))
result = float('inf')


for commands in permutations(command_list):

    move_arr = [row[:] for row in arr]
    for command in commands:
        rotate(command,move_arr)
    arr_min = min(list(map(sum,move_arr)))
    result = min(arr_min,result)
print(result)

from itertools import permutations
import sys
input = sys.stdin.readline
def play(entry):
    out_count = 0
    innings = 0
    cu_player_ind = 0
    # 1루,2루,3루
    score = 0
    base1,base2,base3 = 0,0,0
    while innings < N:
        while out_count<3:
            if arr[innings][entry[cu_player_ind]-1] == 0:
                out_count += 1
            elif arr[innings][entry[cu_player_ind]-1] == 1:
                
                score += base3
                base1,base2,base3 = 1,base1,base2
            elif arr[innings][entry[cu_player_ind]-1] == 2:
                score += (base2+base3)
                base1,base2,base3 = 0,1,base1
            elif arr[innings][entry[cu_player_ind]-1] == 3:
                score += (base1+base2+base3)
                base1,base2,base3 = 0,0,1
            else:
                score = score + base1+base2+base3 + 1
                base1,base2,base3 = 0,0,0
            cu_player_ind = (cu_player_ind+1)%9
        out_count = 0
        base1,base2,base3 = 0,0,0
        innings += 1
    return score





N = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
result = 0
for _players in permutations(range(2,10)):
    _players = list(_players)
    players = _players[:3]+[1] + _players[3:]
    temp = play(players)
    if result <temp:
        result = temp
print(result)

from itertools import permutations
import sys
input = sys.stdin.readline

N = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
result = 0
for _players in permutations(range(2,10)):
    _players = list(_players)
    players = _players[:3]+[1] + _players[3:]
    cu_player_ind = 0
    # 1루,2루,3루
    score = 0
    for innings in arr:
        out_count = 0
        base1,base2,base3 = 0,0,0
        while out_count<3:
            if innings[players[cu_player_ind]-1] == 0:
                out_count += 1
            elif innings[players[cu_player_ind]-1] == 1:
                
                score += base3
                base1,base2,base3 = 1,base1,base2
            elif innings[players[cu_player_ind]-1] == 2:
                score += (base2+base3)
                base1,base2,base3 = 0,1,base1
            elif innings[players[cu_player_ind]-1] == 3:
                score += (base1+base2+base3)
                base1,base2,base3 = 0,0,1
            else:
                score = score + base1+base2+base3 + 1
                base1,base2,base3 = 0,0,0
            cu_player_ind = (cu_player_ind+1)%9
    if score > result:
        result = score
print(result)

def dfs(x,y,cnt):
    global result
    if cnt > result:
        return
    if x >= 10:
        result = min(result,cnt)
        return
    if y >= 10:
        dfs(x+1,0,cnt)
        return
    if arr[x][y] == 1:
        for paper_size in range(5,0,-1):
            if paper[paper_size]:
                if x + paper_size <= 10 and y + paper_size <= 10:
                    flag = False
                    for dx in range(paper_size):
                        for dy in range(paper_size):
                            if not arr[x+dx][y+dy]:
                                flag = True
                                break
                        if flag:
                            break
                    if not flag:
                        for dx in range(paper_size):
                            for dy in range(paper_size):
                                arr[x+dx][y+dy] = 0
                        paper[paper_size] -= 1
                        dfs(x,y+paper_size-1,cnt+1)
                        paper[paper_size] += 1
                        for dx in range(paper_size):
                            for dy in range(paper_size):
                                arr[x+dx][y+dy] = 1
    else:
        dfs(x,y+1,cnt)

        


arr = [list(map(int,input().split())) for _ in range(10)]
paper = [0]+[5]*5
result = float('inf')
dfs(0,0,0)
print(result if result != float('inf') else -1)

def check(x,y,size):
    if x + size > 10 or y + size >10:
        return False
    for dx in range(size):
        for dy in range(size):
            if not arr[x+dx][y+dy]:
                return False
    return True


def set_position(x,y,size,val):
    for dx in range(size):
        for dy in range(size):
            arr[x+dx][y+dy] = val
def dfs(x,y,cnt):
    global result
    if cnt >= result:
        return
    finish = True
    while x < 10:
        while y < 10:
            if arr[x][y] == 1:
                finish = False
                for paper_size in range(5,0,-1):
                    if paper[paper_size] and check(x,y,paper_size):
                        set_position(x,y,paper_size,0)
                        paper[paper_size] -= 1
                        dfs(x,y+paper_size-1,cnt+1)
                        paper[paper_size] += 1
                        set_position(x,y,paper_size,1)
                return
            y += 1
        x += 1
        y = 0
    if finish:
        result = min(result,cnt)
        


arr = [list(map(int,input().split())) for _ in range(10)]
paper = [0]+[5]*5
result = float('inf')
dfs(0,0,0)
print(result if result != float('inf') else -1)

import sys

input = sys.stdin.readline
def calc_operator(operator,x,y):
    if operator == '*':
        return x*y
    elif operator == '-':
        return x-y
    elif operator == '+':
        return x+y


def calc():
    new_num_list = []
    new_operator_list = []
    ind = 0
    while ind<len(num_list):
        if ind < len(num_list)-1:
            if not open_bracket[ind]:
                new_num_list.append(num_list[ind])
                new_operator_list.append(operator_list[ind])
                ind += 1
            else:
                new_number = calc_operator(operator_list[ind],num_list[ind],num_list[ind+1])
                if ind == len(num_list)-2:
                    new_num_list.append(new_number)
                else:
                    new_num_list.append(new_number)
                    new_operator_list.append(operator_list[ind+1])
                ind += 2
        else:
            new_num_list.append(num_list[ind])
            ind+= 1
    ind = 0
    value = new_num_list[0]
    while ind < len(new_num_list)-1:
        value = calc_operator(new_operator_list[ind],value,new_num_list[ind+1])
        ind += 1
    return value







def dfs(index):
    global result
    if index == len(num_list)-1:
        result = max(calc(),result)
        return
    else:
        if visited[index]:
            visited[index] = False
            visited[index+1] = False
            open_bracket[index] = True
            dfs(index+1)
            visited[index] = True
            visited[index+1] = True
            open_bracket[index] = False
        dfs(index+1)

N = int(input())
arr = list(input())
if N == 1:
    print(arr[0])
else:
    num_list = []
    operator_list = []
    for i in range(N):
        if i%2:
            operator_list.append(arr[i])
        else:
            num_list.append(int(arr[i]))
    result = -float('inf')
    visited = [True]*len(num_list)
    open_bracket = [False]*len(num_list)
    dfs(0)
    print(result)

import sys

input = sys.stdin.readline
def calc(operator,x,y):
    if operator == '*':
        return x*y
    elif operator == '-':
        return x-y
    elif operator == '+':
        return x+y
def dfs(idx,value):
    global result
    if idx == length_num-1:
        result = max(result,value)
        return
    temp = calc(operator_list[idx],value,num_list[idx+1])
    dfs(idx+1,temp)

    if idx < length_num-2:
        next_value = calc(operator_list[idx+1],num_list[idx+1],num_list[idx+2])
        temp = calc(operator_list[idx],value,next_value)
        dfs(idx+2,temp)



N = int(input())
origin_input = list(input().strip())
num_list = []
operator_list = []

for ind in range(len(origin_input)):
    if ind%2:
        operator_list.append(origin_input[ind])
    else:
        num_list.append(int(origin_input[ind]))
result = -float('inf')
length_num = len(num_list)

dfs(0,num_list[0])
print(result)

def find_arr(arr):
    global result
    for bit_mask in range(2**8):
        copy_arr = [row[:] for row in arr]
        change_bit = str(bin(bit_mask))[2:].count('1')
        if result < change_bit:
            continue
        for row in range(3):
            if bit_mask & (1<<row):
                for col in range(3):
                    copy_arr[row][col] = (copy_arr[row][col]+1)%2

        for col in range(3):
            if bit_mask & (1<<(col+3)):
                for row in range(3):
                    copy_arr[row][col] = (copy_arr[row][col]+1)%2


        if bit_mask & (1<<6):
            for row in range(3):
                copy_arr[row][row] = (copy_arr[row][row]+1)%2

        if bit_mask & (1<<7):
            for row in range(3):
                copy_arr[row][2-row] = (copy_arr[row][2-row]+1)%2

        sum_temp = sum(list(map(sum,copy_arr)))
        if sum_temp == 9 or sum_temp == 0:
            result = change_bit






T = int(input())



for tc in range(T):
    arr = []
    result = float('inf')
    for _ in range(3):
        s = list(input().split())
        for i in range(3):
            if s[i] == 'T':
                s[i] = 1
            else:
                s[i] = 0
        arr.append(s)
    
    cnt = 0

    find_arr(arr)
    print(-1 if result == float('inf') else result)

def checkminNumber(index,open1,open2):
    if index > M-1:
        return 0 
    result = dp[index][open1][open2]
    if result != float('inf'):
        return result
    next_open = output_list[index]
    dp[index][open1][open2] = min(abs(open1 - next_open) + checkminNumber(index+1,next_open,open2), abs(open2 - next_open) + checkminNumber(index+1,open1,next_open))
    return dp[index][open1][open2]



N = int(input())

open1,open2 = list(map(int,input().split()))

M = int(input())
dp = [[[float('inf')]*(N+1) for _ in range(N+1)] for _ in range(M)]
output_list = []

for _ in range(M):
    output_list.append(int(input()))
print(checkminNumber(0,open1,open2))