[Samsung] 2021-2 오후 2번 Sam의 피자 학교

April 5, 2023

[Samsung] 2021-2 오후 2번 Sam의 피자 학교

Question

Language: Python

Difficulty: Platinum 5

해당 문제은 시뮬레이션 유형의 문제로 아래의 과정들이 이루어진다.

가장 작은 밀가루가 포함된 위치에 밀가루 추가
도우 말기
도우 눌러주기
도우 반으로 두번 접기
3번 과정 진행

위의 각 과정들을 자세히 살펴보자

가장 작은 밀가루가 포함된 위치에 밀가루 추가

최소 밀가루 값을 찾아서 같은 값을 가진 위치에 1씩 추가한다.

def add_flour():
    global flours
    min_flour=min(flours)

    for i in range(n):
        if flours[i]==min_flour:
            flours[i]+=1

도우 말기

rolling_dough1 rolling_dough2

위 그림과 같이 도우를 마는 과정은 아래와 같이 정의할 수 있다.

rows,cols 값은 순차적으로 증가하게 되며, 해당 부분을 옮기는 과정을 진행할때 평행이동을 수행하면 된다. (n-1-row,starting_col-col)의 좌표를 (n-2-col,starting_col+row)로 옮겨주는 평행이동을 수행하게 되면 원하는 도우 말기의 결과가 도출된다.starting_col은 바닥의 시작점이다

def roll_flour(flours):
    flour_map=[[0] * n for _ in range(n)]

    #2차원 맵에 도우 나타내기
    for i in range(n):
        flour_map[n-1][i]=flours[i]

    #쌓아올려야 되는 부분
    rows,cols=1,1
    
    #바닥이 시작되는 부분
    starting_col=1

    for index in range(n):
        #바닥에 있는 도우보다 올려야되는 밀가루의 너비가 더 큰 경우 빠져나온다.
        if rows > (n-starting_col):
            break
        starting_row=n-2
        #쌓아올리는 작업 진행 1층 쌓아올리는 작업 진행
        for col in range(cols):
            for row in range(rows):
                flour_map[n-2-col][starting_col+row]=flour_map[n-1-row][starting_col-1-col]
                flour_map[n-1-row][starting_col-1-col]=0

        #다음 바닥의 시작 위치 초기화
        starting_col+=rows
        
        #다음에 말아올려지는 밀가루 부분의 행,열 조정
        if index % 2==0:
            rows+=1
        else:
            cols+=1
        
    #이차원 도우 맵과 도우가 시작되는 행의 값을 반환
    return flour_map,n-((rows-1)*cols)

도우 눌러주기

상하좌우 인접한 밀가루를 비교하면서 차이가 5보다 큰 경우 5로 나누는 나머지 값만큼 큰값에서 빼주고, 작은 값에는 더해준다. 항상 밀가루가 많은 양에서 적은 양으로의 이동만을 고려해서 중복된 밀가루 이동을 피한다.

그런 다음, 말려진 도우를 1차원 형태로 풀어주는 작업을 수행한다.

def push_flour(flour_map,start_col):
    global flours
    difference_map=[[0]*n for _ in range(n)]

    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    #밀가루의 이동
    for row in range(n-1,-1,-1):
        for col in range(start_col,n):
            current_value=flour_map[row][col]
            #밀가루가 있는 칸이 있는 칸인지 확인
            if current_value ==0:
                continue

            for dir in range(4):
                next_row=row+dy[dir]
                next_col=col+dx[dir]

                #경계를 벗어나는지 확인
                if not check_range(next_row,next_col) or flour_map[next_row][next_col] == 0:
                    continue
            
                next_value=flour_map[next_row][next_col]

                #큰쪽 에서 작은쪽으로만 고려해서 중복으로 적용되지 않도록 한다.
                if current_value < next_value:
                    continue
                
                #인접한 부분과의 차이가 5보다 작으면 변하지 않기 때문에 넘어간다.
                difference=abs(next_value-current_value)
                if difference < 5:
                    continue
                
                transitition_value=difference // 5
                
                #큰쪽은 빼주고, 작은쪽은 더해준다.
                difference_map[row][col]-=transitition_value
                difference_map[next_row][next_col]+=transitition_value

    #밀가루의 변화량을 적용하고 밀가루를 펴주는 작업
    index=0       
    for col in range(start_col,n):
        for row in range(n-1,-1,-1):
            flour=flour_map[row][col]
            if flour==0:
                continue
            flour+=difference_map[row][col]//2
            flours[index]=flour
            index+=1

도우 반으로 두번 접기

folding_dough folding_dough2

도우를 반으로 접는 과정은 도우를 말아주는 작업과 마찬가지로, rows,cols을 늘려주면서 기존의 좌표에서 이동하는 좌표로 평행이동 시키면 된다. 위의 경우 (n-rows+row,starting_col-1-col)의 좌표를 (starting_row,starting_col+col)로 평행이동을 취한다.starting_col은 바닥의 시작점, starting_row는 올라가는 높이이다.

def fold_flour():
    flour_map=[[0] * n for _ in range(n)]

    #2차원 맵에 도우 나타내기
    for i in range(n):
        flour_map[n-1][i]=flours[i]

    
    #쌓아올려야 되는 부분
    rows,cols=1,n//2
    
    #바닥이 시작되는 부분
    starting_col=n//2
    starting_row=n-2
    for i in range(2):
        for row in range(rows):
            for col in range(cols):
                flour_map[starting_row][starting_col+col]=flour_map[n-rows+row][starting_col-1-col]
                flour_map[n-rows+row][starting_col-1-col]=0
            starting_row-=1
        
        rows*=2
        cols//=2

        starting_col+=cols
    
    return flour_map,n-n//4

Solution

#최솟값을 가진 밀가루 양에 1씩 추가하기
def add_flour():
    global flours
    min_flour=min(flours)

    for i in range(n):
        if flours[i]==min_flour:
            flours[i]+=1

#도우를 말아주는 작업
def roll_flour(flours):
    flour_map=[[0] * n for _ in range(n)]

    #2차원 맵에 도우 나타내기
    for i in range(n):
        flour_map[n-1][i]=flours[i]

    #쌓아올려야 되는 부분
    rows,cols=1,1
    
    #바닥이 시작되는 부분
    starting_col=1

    for index in range(n):
        #바닥에 있는 도우보다 올려야되는 밀가루의 너비가 더 큰 경우 빠져나온다.
        if rows > (n-starting_col):
            break
        starting_row=n-2
        #쌓아올리는 작업 진행 1층 쌓아올리는 작업 진행
        for col in range(cols):
            for row in range(rows):
                flour_map[n-2-col][starting_col+row]=flour_map[n-1-row][starting_col-1-col]
                flour_map[n-1-row][starting_col-1-col]=0

        #다음 바닥의 시작 위치 초기화
        starting_col+=rows
        
        #다음에 말아올려지는 밀가루 부분의 행,열 조정
        if index % 2==0:
            rows+=1
        else:
            cols+=1
        
    #이차원 도우 맵과 도우가 시작되는 행의 값을 반환
    return flour_map,n-((rows-1)*cols)

#밀가루를 눌러주는 작업
def push_flour(flour_map,start_col):
    global flours
    difference_map=[[0]*n for _ in range(n)]

    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    #밀가루의 이동
    for row in range(n-1,-1,-1):
        for col in range(start_col,n):
            current_value=flour_map[row][col]
            #밀가루가 있는 칸이 있는 칸인지 확인
            if current_value ==0:
                continue

            for dir in range(4):
                next_row=row+dy[dir]
                next_col=col+dx[dir]

                #경계를 벗어나는지 확인
                if not check_range(next_row,next_col) or flour_map[next_row][next_col] == 0:
                    continue
            
                next_value=flour_map[next_row][next_col]

                #큰쪽 에서 작은쪽으로만 고려해서 중복으로 적용되지 않도록 한다.
                if current_value < next_value:
                    continue
                
                #인접한 부분과의 차이가 5보다 작으면 변하지 않기 때문에 넘어간다.
                difference=abs(next_value-current_value)
                if difference < 5:
                    continue
                
                transitition_value=difference // 5
                
                #큰쪽은 빼주고, 작은쪽은 더해준다.
                difference_map[row][col]-=transitition_value
                difference_map[next_row][next_col]+=transitition_value

    #밀가루의 변화량을 적용하고 밀가루를 펴주는 작업
    index=0       
    for col in range(start_col,n):
        for row in range(n-1,-1,-1):
            flour=flour_map[row][col]
            if flour==0:
                continue
            flour+=difference_map[row][col]//2
            flours[index]=flour
            index+=1

#도우를 반으로 두 번 접기
def fold_flour():
    flour_map=[[0] * n for _ in range(n)]

    #2차원 맵에 도우 나타내기
    for i in range(n):
        flour_map[n-1][i]=flours[i]

    
    #쌓아올려야 되는 부분
    rows,cols=1,n//2
    
    #바닥이 시작되는 부분
    starting_col=n//2
    starting_row=n-2
    for i in range(2):
        for row in range(rows):
            for col in range(cols):
                flour_map[starting_row][starting_col+col]=flour_map[n-rows+row][starting_col-1-col]
                flour_map[n-rows+row][starting_col-1-col]=0
            starting_row-=1
        
        rows*=2
        cols//=2

        starting_col+=cols
    
    return flour_map,n-n//4

        
def check_range(row,col):
    if row < 0 or row >=n or col < 0 or col>=n:
        return False
    return True


def solution():
    time=0

    while True:
        #최대 최소의 차이가 k이하인 경우 탈출
        if max(flours) - min(flours) <=k:
            break
        add_flour()
        #도우 말기
        flour_map,start_col=roll_flour(flours)
        #도우 눌러주기
        push_flour(flour_map,start_col)
        #도우를 반으로 두 번 접기
        flour_map,start_col=fold_flour()
        #도우 눌러주기
        push_flour(flour_map,start_col)
        time+=1
    
    print(time)
    
if __name__ == "__main__":
    n,k=map(int,input().split())
    flours=list(map(int,input().split()))

    solution()

Twitter Facebook LinkedIn

Jehyun Jung

[Samsung] 2021-2 오후 2번 Sam의 피자 학교

[Samsung] 2021-2 오후 2번 Sam의 피자 학교

Question

Language: Python

Difficulty: Platinum 5

Solution

공유하기

댓글남기기

참고

Typescript Module Issue

Changing Java Version in Linux

[BOJ] Q1725 히스토그램

[Programmers] Q176962 과제 진행하기