[Baekjoon] 12100. 2048 (Easy) [G2]


📚 質問する


https://www.acmicpc.net/problem/12100

📖 に答える


四つの方向に移動して、全部で5回すればいいので、組み合わせで解決します.

くみあわせかんすう


再帰関数を用いて組合せを実現する.
5回回ると最高価格が確認されます.
このとき傾斜すると配列の値が変化するため、[:]の浅いコピーを使用して復元する必要があります.

アレイを時計回りに90度回転させる関数


あなたの方向に移動するよりも、回転して並べたほうがいいです.
90度回転すると、点火式を探すために下図のように描きます.(略図...)

配列の値を前の配列の値に保存し、新しい配列に90度回転します.arr[i][j] = arr2[n-j-1][i]4方向です.全部で3回回ればいいです.

左にのみ移動する関数


4つの方向のうち左側の理由は、左に傾いた後、滑走路を通って各行を挿入するのが便利だからです.
マージの方法は次のとおりです.
  • 0以外の値を配列に入れます.(特に配列されていない要素の場合は、そのまま読み込みます.)
  • までにBoolean flagを作成して合わせを確認するときは、必ず次回が合わないように設定してください.
  • まではマージされておらず、配列の末尾値が現在確認されている値と同時にマージされます.
  • 寄せ集めた配列を0にします.
    行ごとにやる.

    最も高価な関数の決定


    最高価格を確認するのは簡単です.
    2 D配列を巡回して、最低価格を見つければいいです.

    📒 コード#コード#

    def recur(cur):
        global arr, max_result
        if cur == 5:    # 5번 기울인 후 확인
            max_result = max(check(), max_result)
            return
        arr_origin = [arr[i][:] for i in range(n)]      # 원본 값 저장
        move()                                          # 기울이기
        recur(cur + 1)
        for _ in range(3):
            arr = [arr_origin[i][:] for i in range(n)]      # 기울이기 전으로 되돌린다.
            turn()                                          # 90도 회전
            arr_origin = [arr[i][:] for i in range(n)]      # 원본 값 저장
            move()                                          # 기울이기
            recur(cur + 1)
    
    
    def turn():     # 시계 방향으로 90도 배열을 돌린다.
        arr_origin = [arr[i][:] for i in range(n)]
        for i in range(n):
            for j in range(n):
                arr[i][j] = arr_origin[n-j-1][i]
    
    
    def move():     # 왼쪽으로 기울인다.
        for i in range(n):
            blocks = []     # 행 별로 블록들을 합쳐준다.
            sum_flag = 0    # 합친 블록인지 표시
            for j in range(n):  # 왼쪽부터 블록들을 확인한다.
                block = arr[i][j]
                if not block:   # 비어있는 경우
                    continue
                # 이전 블록을 합치지 않고, 이전 블록 값과 같은 경우
                if sum_flag == 0 and blocks and blocks[-1] == block:
                    blocks[-1] = block * 2
                    sum_flag = 1    # 합친 블록이라고 표시
                else:
                    sum_flag = 0    # 새로 넣어주니 합치지 않았다고 표시
                    blocks.append(block)    # 새로 넣어준다.
            blocks += [0] * (n - len(blocks))
            arr[i] = blocks[:]
    
    
    def check():    # 최댓값을 확인해 현재 최대값보다 큰지 확인한다.
        mmax = 0
        for i in range(n):
            for j in range(n):
                mmax = max(mmax, arr[i][j])
        return mmax
    
    
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    max_result = 0
    recur(0)
    print(max_result)

    🔍 結果