주사위의 움직임에 집중해서 설명한다. 나머지 조건은 어렵지 않으므로 생략한다. 주사위는 아래와 같이 2차원 배열로 표현한다.

"""
dice[0][1] == 뒷면
dice[1][0] == 좌측면
dice[1][1] == 윗면
dice[1][2] == 우측면
dice[2][1] == 앞면
dice[3][1] == 밑면
"""
dice = [
    [0,2,0],
    [4,1,3],
    [0,5,0],
    [0,6,0]
]

여기서 밑면은 dice[3][1]이다. 주사위를 만들었으니 주사위를 동서남북으로 움직여보자.

동쪽방향

주사위를 동쪽 방향으로 움직이면 주사위 윗면이 우측면으로, 우측면은 밑면으로, 밑면은 좌측면으로 좌측면은 윗면으로 이동한다. 앞면과 뒷면은 그대로이다. 이를 코드로 표현하면 다음과 같다.

tmp = dice[1][2]
for i in range(2, 0, -1): dice[1][i] = dice[1][i-1]
dice[1][0] = dice[3][1]
dice[3][1] = tmp

서쪽방향

주사위를 서쪽방향으로 이동하면 윗면이 좌측면으로, 좌측면은 밑면으로, 밑면은 우측면으로, 우측면은 윗면으로 이동한다. 이를 코드로 표현하면 다음과 같다.

tmp = dice[1][0]
for i in range(0, 2): dice[1][i] = dice[1][i+1]
dice[1][2] = dice[3][1]
dice[3][1] = tmp

북쪽방향

주사위를 북쪽방향으로 이동하면, 윗면은 뒷면으로 뒷면은 밑면으로, 밑면은 앞면으로 앞면은 윗면으로 이동한다. 좌측면과 우측면은 그대로이다. 이를 코드로 표현하면 다음과 같다.

tmp = dice[0][1]
for i in range(0, 3): dice[i][1] = dice[i+1][1]
dice[3][1] = tmp

남쪽방향

주사위를 남쪽방향으로 이동하면, 앞면은 밑면으로, 밑면은 뒷면으로, 뒷면은 윗면으로, 윗면은 앞면으로 이동한다. 좌측면과 우측면은 그대로이다. 이를 코드로 표현하면 다음과 같다.

tmp = dice[3][1]
for i in range(3, 0, -1): dice[i][1] = dice[i-1][1]
dice[0][1] = tmp

주사위 이동을 구현했으면 나머지는 조건에 따라 구현해주면된다.

2.코드

from collections import deque

NORTH = 0
EAST = 1
SOUTH = 2
WEST = 3

r, c, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(r)]
d = ((-1,0), (0,1), (1,0), (0,-1))
dice = [
    [0,2,0],
    [4,1,3],
    [0,5,0],
    [0,6,0]
]

def move_dice(to):
    if to == NORTH:
        tmp = dice[0][1]
        for i in range(0, 3): dice[i][1] = dice[i+1][1]
        dice[3][1] = tmp

    elif to == EAST:
        tmp = dice[1][2]
        for i in range(2, 0, -1): dice[1][i] = dice[1][i-1]
        dice[1][0] = dice[3][1]
        dice[3][1] = tmp

    elif to == SOUTH:
        tmp = dice[3][1]
        for i in range(3, 0, -1): dice[i][1] = dice[i-1][1]
        dice[0][1] = tmp

    elif to == WEST:
        tmp = dice[1][0]
        for i in range(0, 2): dice[1][i] = dice[1][i+1]
        dice[1][2] = dice[3][1]
        dice[3][1] = tmp

def isin(y, x):
    if -1<y<r and -1<x<c: return True
    return False 

def move(y, x, to):
    ny = y + d[to][0]
    nx = x + d[to][1]
    if not isin(ny, nx):
        if to == EAST: to = WEST
        elif to == WEST: to = EAST
        elif to == NORTH: to = SOUTH
        elif to == SOUTH: to = NORTH
        ny = y + d[to][0]
        nx = x + d[to][1]

    move_dice(to)
    return ny, nx, to

def get_next_direction(sy, sx, to):
    if arr[sy][sx] > dice[3][1]: return to-1 if to > 0 else WEST
    elif arr[sy][sx] < dice[3][1]: return (to+1) % 4
    return to

def get_score(sy, sx):
    q = deque()
    visited = [[False]*c for _ in range(r)]
    q.append((sy,sx))
    visited[sy][sx] = True
    cnt = 1

    while q:
        y, x = q.popleft()

        for dy, dx in d:
            ny = y + dy
            nx = x + dx
            if not isin(ny, nx): continue
            if not visited[ny][nx] and arr[ny][nx] == arr[sy][sx]:
                visited[ny][nx] = True
                cnt += 1
                q.append((ny,nx))

    return cnt

to = EAST
y, x = 0, 0
answer = 0
while k:
    y, x, to = move(y, x, to)
    answer += get_score(y, x) * arr[y][x]
    to = get_next_direction(y, x, to)
    k -= 1

print(answer)

1. 아이디어

불에 관한 정보를 배열에 저장하지 않고 딕셔너리에 저장했다. 딕셔너리의 key는 불이 있는 좌표고 value는 tuple(질량, 속력, 방향)을 저장하는 리스트이다. value의 타입이 리스트인 이유는 하나의 좌표에서 다수의 불이 존재할 수 있기 때문이다.

각 불의 좌표(key)에 대해, value에 있는 모든 정보를 각 정보에 의해 이동된 불의 좌표(key)에대한 value에 저장한다. 저장하는 과정은 사본 딕셔너리를 만들어서, 불의 이동 결과를 사본 딕셔너리에 저장했다. 모든 이동이 끝났으면, 사본 딕셔너리의 정보를 원본 딕셔너리에 반영했다.

불의 이동이 반영된 딕셔너리를 활용하여, 불을 합치고 나누는 과정을 구하면된다. 문제에 제시된 조건대로 구현하면 된다.

2. 코드

```python n, m, k = map(int, input().split()) fires = {} v = ((-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1))

for _ in range(m): y, x, m, s, d = map(int, input().split()) y, x = y-1, x-1 if (y, x) in fires.keys(): fires[(y,x)].append((m, s, d)) else: fires[(y,x)] = [(m,s,d)]

def move_fires(): _dict = {} for y, x in fires.keys(): while fires[(y,x)]: m, s, d = fires[(y,x)].pop() ny = (y + v[d][0] * s) % n nx = (x + v[d][1] * s) % n if (ny,nx) not in _dict.keys(): _dict[(ny,nx)] = [(m,s,d)] else: _dict[(ny,nx)].append((m,s,d))

for y, x in _dict.keys():
    while _dict[(y,x)]:
        m, s, d = _dict[(y,x)].pop()
        if (y, x) not in fires.keys(): fires[(y,x)] = [(m,s,d)]
        else: fires[(y,x)].append((m,s,d))

def divide_fires(): for y, x in fires.keys(): total_m, total_s, odds = [0]*3 size = len(fires[(y,x)]) if size == 1: continue

    while fires[(y,x)]:
        m, s, d = fires[(y,x)].pop()
        total_m += m
        total_s += s
        if d % 2 == 1: odds += 1

    total_m //= 5
    if not total_m: continue
    total_s //= size
    k = []
    if odds == 0 or odds == size: k = [i for i in range(0, 8, 2)]       
    else: k = [i for i in range(1, 9, 2)]
    for i in k: fires[(y,x)].append((total_m, total_s, i))

while k: move_fires() divide_fires() k -= 1

answer = 0 for y, x in fires.keys(): while fires[(y,x)]: m, _, _ = fires[(y,x)].pop() answer += m

print(answer)

문제에서 제시된 내용대로 따라 구현하면된다. 블록 그룹의 경우 딕셔너리를 활용했다. key는 블록 그룹의 기준 블록을 가리키는 좌표이고 value는 해당 그룹에 속하는 블록들의 좌표들이 들어있는 리스트이다. 격자의 (0,0) 부터 (n-1, n-1)까지 순차적으로 탐색한다. 탐색을 하면서 해당 좌표가 일반 블록이고 처음 방문하는 것이라면, key로 들어가는 기준 블록은 항상 기준 블록의 조건을 만족한다.

무지개 블록의 경우, 1개의 무지개 블록은 여러개의 블록 그룹에 소속될 수 있다. 따라서, 블록 그룹을 만든 후, 방문 처리된 무지개 블록의 좌표를 방문 처리하지 않은 것으로 설정한다.

위의 과정으로부터 형성된 블록 그룹 중, 기준 블록만 갖고 있는 블록 그룹들을 모두 제거한다. 그리고 해당 좌표를 방문하지 않는 것으로 설정한다.

블록 그룹을 만드는데 성공했으면, 그 중 가장 큰 블록 그룹을 찾고 문제에 제시된 내용처럼 점수를 구하고 그 부분들을 제거한다. 이후 중력 작용과 90도 반시계 방향 회전, 다시 중력 작용을 하면된다. 이 부분은 그냥 구현이기 때문에 구체적인 설명은 생략한다.

위에서 언급된 과정을 블록 그룹이 하나도 없을 때까지 반복하고, 각 과정에서 얻은 점수를 합산하여 출력한다.

2. 코드

EMPTY = -2
BLACK = -1
RAINBOW = 0

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
groups = {}
answer = 0

def isin(y,x):
    if -1<y<n and -1<x<n: return True
    return False

def make_groups():
    global groups, arr
    visited = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if arr[i][j] in (EMPTY, BLACK, RAINBOW): continue
            if not visited[i][j]:
                visited[i][j] = True
                groups[(i,j)] = []
                _make_groups(visited, i, j)
                if not groups[(i,j)]: del groups[(i,j)]
                visited[i][j] = False
                set_rainbow_false(visited)

def _make_groups(visited, sy, sx):
    global groups, arr
    q = []
    q.append((sy, sx))
    d = ((1,0), (-1,0), (0,-1), (0,1))
    while q:
        y, x = q[0]
        del q[0]

        for dy, dx in d:
            ny = y + dy
            nx = x + dx
            if not isin(ny, nx): continue
            if arr[ny][nx] not in (arr[sy][sx], RAINBOW): continue
            if not visited[ny][nx]:
                visited[ny][nx] = True
                groups[(sy,sx)].append((ny, nx))
                q.append((ny, nx))

def set_rainbow_false(visited):
    global arr
    for i in range(n):
        for j in range(n):
            if arr[i][j] == RAINBOW: visited[i][j] = False

def find_biggest_group():
    global groups
    k, size = (-1,-1), 0
    for key, value in groups.items():
        t = len(value)
        if size < t+1: k, size = key, t+1
        elif size == t+1:
            rain1 = get_rainbow_size(k)
            rain2 = get_rainbow_size(key)
            if rain1 < rain2: k, size = key, t+1
            elif rain1 == rain2: k, size = key, t+1

    return k, size

def get_rainbow_size(key):
    global groups
    cnt = 0
    for y, x in groups[key]:
        if arr[y][x] == RAINBOW: cnt += 1
    return cnt

def score():
    global groups
    key, cnt = find_biggest_group()
    arr[key[0]][key[1]] = EMPTY
    for y, x in groups[key]: arr[y][x] = EMPTY
    return cnt**2

def gravity():
    global arr
    for x in range(n):
        for y in range(n-1, -1, -1):
            if arr[y][x] == BLACK: continue
            _gravity(y, x)

def _gravity(sy, sx):
    global arr
    for y in range(sy+1, n):
        if arr[y][sx] == EMPTY: arr[y-1][sx], arr[y][sx] = arr[y][sx], arr[y-1][sx]
        else: break

def rotate():
    global arr
    stack = []
    for i in range(n):
        for j in range(n):
            stack.append(arr[i][j])

    for x in range(n-1, -1, -1):
        for y in range(n):
            arr[y][x] = stack.pop()

while True:
    groups = {}
    make_groups()
    if not groups: break
    answer += score()
    gravity()
    rotate()
    gravity()

print(answer)

1번째 날에 호랑이가 떡을 먹은 개수를 a, 2번째 날에 떡을 먹은 개수를 b라고 하자. 그러면 3번째 날에 떡을 먹은 개수는 a+b, 4번째 날에 떡을 먹은 개수는 a+2b, 5번째 날에 떡을 먹은 개수는 2a+3b, 6번째 날에 떡을 먹은 개수는 3a+5b... 이런식으로 계속 진행하여 d번째 날에 떡을 먹은 개수를 구한다.

d번째 날에 떡을 먹은 개수를 pa+qb라고하자. 그러면 pa+qb=k이다. 이는 qb=k-pa와 같다. 다시말해 k-pa은 q로 나누어 떨어져야한다.(i.e. (k-pa) % q == 0) 이러한 k-pa를 구하기 위해, a를 1부터 대입하여 1씩 증가시켜q로 나누어떨어지는지 확인해본다.

2.코드

```python import sys

d, k = map(int, sys.stdin.readline().rsplit()) first = [1,0] second = [0,1] p, q = 0, 0

for i in range(3, d+1): p = first[0] + second[0] q = first[1] + second[1] first = second[:] second = [p, q]

a = 1 while True: x = p * a y = k - x if y % q == 0: print(a) print(y//q) break

a += 1

어떻게 접근할 지 몰라서 해설을 봤다. 공식 해설을 참조했다. a의 모든 원소의 합이 0이되는 지 확인한다음, 0이 아니면 -1를 리턴하고 0이면 edges를 이용하여 트리를 만든다. 이후, 임의의 노드를 1번째로 탐색할 노드로 선택해서 dfs한다. dfs에서 나온 결과를 a에 더하고, 절대 값을(dfs에서 나온 결과)을 카운트한다.

해설에 따르면 덧셈의 교환법칙 때문에, 연산 순서를 정할 필요가 없다고한다. 따라서 작성된 코드의 경우, 임의의 노드로 0을 1번째로 탐색할 노드로 선택했다.

2. 코드

```python from collections import defaultdict import sys

sys.setrecursionlimit(int(1e6)) tree = defaultdict(list) visited = [] arr = [] cnt = 0

def dfs(x): global visited, tree, arr, cnt if visited[x]: return 0 visited[x] = True for nx in tree[x]: k = dfs(nx) cnt += abs(k) arr[x] += k

v = arr[x]
arr[x] = 0
return v

def solution(a, edges): global visited, tree, arr, cnt if sum(a) != 0: return -1 n = len(a) visited = [False for _ in range(n)] arr = a for a, b in edges: tree[a].append(b) tree[b].append(a)

dfs(0)

return cnt

sizes를 순회하면서, 세로가 가로보다 크면, 가로와 세로를 바꿔준다. 이후 가로에서 가장 큰 값을 찾고, 세로에서 가장 큰 값을 찾는다. 그리고 이들을 곱해준다.

2.코드

def solution(sizes):
    for i in range(len(sizes)):
        if sizes[i][0] < sizes[i][1]: sizes[i][0], sizes[i][1] = sizes[i][1], sizes[i][0]

    w = max(sizes, key=lambda x: x[0])[0]
    h = max(sizes, key=lambda x: x[1])[1]
    return w*h

grid의 길이가 전체 칸의 행의 길이, grid안 의 문자열 길이가 전체 칸의 열 길이와 같다. 예를 들어, grid가 ["SR". "LR"]이면 그래프는 아래와 같다.

그 다음 고려해야할 것은 방향이다. 예를 들어 초기 진입으로 1행 1열에 해당하는 S에 들어갈 때, ↓방향으로 S에 진입 또는 →방향으로 S에 진입하는 경우가 있다. 다시말해, 방향을 고려하며 각 칸에 대한 방문 여부를 처리를 해야한다.

S에 방문을 했으면, 어디로 가야할 지 결정해야한다. 이 때, S에 들어온 방향을 고려해야 한다. 예를들어 ↓방향으로 S에 들어왔으면, 다음으로 갈 칸은 2행 1열에 해당하는 L이다. →방향으로 S에 들어왔으면, 다음으로 갈 칸은 1행 2열에 해당하는 L이다. 그리고 그 다음으로 가야할 곳을 문제의 조건을 고려하여 정한다.

위의 과정을 bfs로 구현한다. 어떤 방향으로 어떤 칸을 처음 방문할 때마다, 방문한 칸 수를 증가시킨다.(방향 고려) 어떤 방향으로 어떤 칸을 재방문하게 되면, bfs를 중단하고 지금까지 세어본 칸 수를 리스트에 저장한다.

2. 코드

```python from collections import deque

visited = [] r, c = 0, 0 NORTH = 0 SOUTH = 1 EAST = 2 WEST = 3

def get_next_step(to, y, x): if to == NORTH: return y-1, x elif to == SOUTH: return y+1, x elif to == WEST: return y, x-1 else: return y, x+1

def get_next_to(to, ny, nx, grid): if to == NORTH: if grid[ny][nx] == 'L': return WEST elif grid[ny][nx] == 'S': return NORTH elif grid[ny][nx] == 'R': return EAST

elif to == SOUTH:
    if grid[ny][nx] == 'L': return EAST
    elif grid[ny][nx] == 'R': return WEST
    else: return SOUTH

elif to == EAST:
    if grid[ny][nx] == 'L': return NORTH
    elif grid[ny][nx] == 'R': return SOUTH
    else: return EAST

else:
    if grid[ny][nx] == 'L': return SOUTH
    elif grid[ny][nx] == 'R': return NORTH
    else: return WEST

def bfs(grid, sy, sx, sto): global r, c, visited visited[sy][sx][sto] = True q = deque() cnt = 1 q.append((sy, sx, sto, cnt))

while q:
    y, x, to, cnt = q.popleft()
    ny, nx = get_next_step(to, y, x)
    if ny <= -1: ny = r-1
    elif ny >= r: ny = 0

    if nx <= -1: nx = c-1
    elif nx >= c: nx = 0
    nto = get_next_to(to, ny, nx, grid)

    if visited[ny][nx][nto]: return cnt
    visited[ny][nx][nto] = True
    q.append((ny, nx, nto, cnt+1))

def solution(grid): global visited, r, c r = len(grid) c = len(grid[0]) visited = [[[False for _ in range(4)] for _ in range(c)] for _ in range(r)] answer = [] for i in range(r): for j in range(c): for k in (NORTH, SOUTH, EAST, WEST): if not visited[i][j][k]: answer.append(bfs(grid, i, j, k))

answer.sort()
return answer

문제의 요구사항대로 구현하면된다. 문제의 조건을 만족한다고 가정할 때, 낮은 값이 왼쪽에 있을 때와 오른쪽에 있을 때, 연속적으로 동일한 낮은 값을 갖는 원소 수를 세는 방법이 서로 다르다. 짧게 설명을 하면, 낮은 값이 왼쪽에 있을 때는 원소 수를 1증가 시키고, 다음 재귀함수로 넘어간다. 그외 별도의 처리는 없다. 낮은 값이 오른쪽에 있을 때는 반복문을 이용해 l개의 연속적으로 동일한 낮은 값을 갖는 원소를 갖는지 확인한다. 다시말해, 한번에 하나씩 세는 방법이 낮은 값이 왼쪽에 있을 때이고, 한번에 임의의 수만큼 세는 방법이 낮은 값이 오른쪽에 있을 때이다.
높은 값과 낮은 값을 알아내는 방법은 이전 값과 현재 값을 비교하면 쉽게 알아낼 수 있고, 그 외 부분은 문제 지문에서 조건이 잘 설명되어있어서, 이를 보면서 풀면된다.

2.코드

```python import sys

n, l = map(int, sys.stdin.readline().rsplit()) arr = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(n)] answer = 0

def solve(y, x, val, cnt): if x == n: return True if arr[y][x] == val: cnt += 1 elif abs(arr[y][x]-val) > 1: return False elif val < arr[y][x]: if cnt < l: return False val = arr[y][x] cnt = 1

elif val > arr[y][x]:
    k = 0
    cnt = 0
    for k in range(x, n):
        if arr[y][k] == arr[y][x]: cnt += 1
        else: break

        if cnt == l: break

    val = arr[y][x]
    if cnt < l: return False
    x = k
    cnt = 0

return solve(y, x+1, val, cnt)

for i in range(n): if solve(i, 1, arr[i][0], 1): answer += 1

arr = [[arr[j][i] for j in range(n)] for i in range(n)] for i in range(n): if solve(i, 1, arr[i][0], 1): answer += 1

print(answer)

n개의 원소들간의 차이가 거의 없으면서 합이 s일때, 각 원소의 곱이 최대가 된다. 따라서 우리가 해야할 일은 각 원소의 차이가 없으면서 합이 s를 이루는 원소들을 찾는 것이 목표다. 원소를 구하기 위한 간단한 방법으로 나눗셈이 있다. s를 n으로 나누면 몫과 나머지가 나온다. 몫은 여기서 하나의 원소고, 나머지는 하나의 원소에서 +1를 할 때 사용된다. 예를들어 n이 3이고 s가 17일 때, 몫은 5, 나머지는 2이다. 몫만 고려했을 때, {5,5,5}가 나온다. 여기서 하나의 원소에 대해, 나머지가 0이 될 때까지 +1연산을 하면 {6,6,5}가 된다. 이후, 문제 요구사항에 맞게 정렬을 취하면된다.

2.코드

```python def solution(n, s): p = s // n if p == 0: return [-1] q = s % n answer = [p] * n k = 0 while q > 0: answer[k%n] += 1 q -= 1 k += 1

answer.sort()
return answer

문제에서 입실과 퇴실이 동시에 이뤄지는 경우가 없다는 사실을 이용하자. 핵심은 현재 회의실에 있는 사람들을 leave의 순서에 맞게 퇴실 시킬 수 있다면, 그 순서만큼 퇴실시키고 그 다음에 입실을 진행하면 된다. 입출력 2번째 예제를 토대로 설명하면 아래와 같다.

현재 회의실에 있는 사람들을 리스트(arr)에 넣어보자. 처음에는 1이왔다. 따라서 arr=[1]이다. 이후, leave에서 누가 먼저 떠나는 지 확인한다. 2가 먼저 떠나지만, 현재 회의실에 있는 사람은 1밖에 없으므로, 회의실에 나가는 사람은 없다.

4가 회의실에 두번째로 들어왔다. arr=[1,4]이다. 따라서 1과 4가 만난다. 이후, leave에서 누가 먼저 떠나는지 확인해보자. 2가 먼저 떠나지만, 현재 2는 회의실에 없다. 따라서 회의실에 나가는 사람은 없다.

2가 회의실에 세번째로 들어왔다. arr=[1,4,2]이다. 따라서 1과4는 2를 만난다. 이후, leave에서 누가 먼저 떠나는지 확인해보자. 2가 먼저 떠나므로 2는 회의실에서 나간다. 그 다음 leave에서 누가 떠나는지 확인해보자. 1이 떠나므로 1은 회의실에서 나간다. 그 다음 누가 떠나는지 확인하면 3인데 3은 회의실에 없다. 결과적으로 회의실에 있는 사람은 4밖에 없다.(arr=[4])

3이 회의실에 들어온다. arr=[4,3]이다 따라서 3,4는 서로 만난다. 이후, leave에서 누가 먼저 떠나는지 확인해보자. 3이 떠나므로, 3은 회의실에서 나간다. 그 다음 leave에서 누가 먼저 떠나는지 확인해보자. 4가 떠나므로, 4는 회의실에서 나간다. 모든 사람이 떠났다.

위의 과정을 진행하면서, 각 사람들이 몇 명을 만났는지 세면된다.

다시말해, 현재 회의실에 있는 사람들을 leave의 순서에 맞춰서 보낼 수 있으면 그 순서만큼 먼저 보내고 입실을 받는 것이다. 코드가 간결한편이 아니므로, 다른 사람들이 푼 풀이를 참고하는 것을 권장한다.

2.코드

def solution(enter, leave):
    arr = []    
    n = len(enter)
    answer = [0] * n
    i, j, = [0] * 2

    while True:
        if j == n: break
        while arr and j < n:
            try:
                x = arr.index(leave[j])
                del arr[x]
                j += 1
            except:
                break

        if i < n:
            arr.append(enter[i])
            i += 1

        if len(arr) > 1:
            for p in arr: answer[p-1] += 1 if answer[p-1] > 0 else len(arr) - 1

    return answer

문제의 조건에 따라 정렬을 할 때 1,2,3은 큰 값이 먼저오고, 4는 작은 값이 먼저온다. 내 코드의 경우, 1,2,3에 음의 부호를 붙여서 정렬했다. 주의해야할 점은 승률을 계산할 때, 소수를 버리거나 반올림하면 안되고, 분모가 0이되는 것도 고려해야한다.(3번째 입출력 참조) 이 부분만 주의해서 풀면된다.
기준에 맞는 정렬을 구현할 때, 정렬을 하나하나 구현할 필요없다. arr=[[-1번승률, -1번이 보다 무거운 복서를 이긴 횟수, -1번 무게, 1번], [-2번승률, -2번이 보다 무거운 복서를 이긴 횟수, -2번 무게, 2번]...]식으로 만들고 arr.sort()하면 된다. 파이썬은 2차원 리스트를 정렬할 때, 각 행의 1번째 원소 값을 먼저 비교하고, 그 값이 같은 행들이 존재하는 경우 그 다음 2번째 원소 값을 갖고 비교하고 2번째 원소 값도 같으면 그 다음으로 가는 식으로 진행해서 정렬한다.

2. 코드

```python arr = []

def make_std(weights, head2head): global arr n = len(weights) for i in range(n): rate = 0 win = 0 lose = 0 heavy_win = 0

    for j in range(n):
        if i == j: continue
        if head2head[i][j] == 'L': lose += 1
        elif head2head[i][j] == 'W':
            win += 1
            if weights[i] < weights[j]: heavy_win += 1

    rate = win * 100 / (win + lose) if win + lose != 0 else 0
    arr.append([-rate, -heavy_win, -weights[i], (i+1)])

def solution(weights, head2head): global arr make_std(weights, head2head) arr.sort() answer = [x[-1] for x in arr] return answer

투 포인터와 슬라이딩 윈도우를 이용해 해결한다. 처음 딱 1번, 연속된 k개 초밥을 선형탐색하여 초밥의 종류 수와 해당 종류를 몇개 먹었는지 카운트한다. 이후 lp, rp를 사용할 것이기 때문에, 반복문이 필요없다.
lp와 rp를 각각 1증가 시키기전에 lp에서 먹은 초밥 개수를 1 차감한다. 이 때, 먹은 초밥의 개수가 0이 되면, 초밥 종류 수를 1 차감한다. 이후 lp, rp를 각 1씩 증가시킨다. rp에있는 초밥 종류를 처음 먹을 때, 초밥 종류수를 1 증가시킨다. 그리고 이 종류에 대한 먹은 초밥 수도 1 증가시킨다.

한편, 구간[lp, rp]에서 쿠폰이 적용되는 초밥 종류가 없으면 초밥 종류 수를 1 증가시킨다.

위의 연산을 lp가 n이 될 때까지 반복한다. 유의해야할 점은 회전 초밥이기 때문에 rp가 인덱스 0을 가리키는 것이 가능하다는 것이다. 이것에 주의해서 구현하면된다.

2. 코드

import sys
from collections import defaultdict

n, d, k, c = map(int, sys.stdin.readline().rsplit())
c = str(c)
arr = [sys.stdin.readline().rstrip() for _ in range(n)]
kinds = defaultdict(int)
lp = 0
rp = lp + k - 1
count = 0
answer = 0
first = True

while lp < n:
    if first:
        for i in range(lp, rp+1):
            i %= n
            sushi = arr[i]
            if not kinds[sushi]: count += 1
            kinds[sushi] += 1
            first = False

        answer = max(answer, count) if kinds[c] else max(answer, count+1)
        continue

    first_sush = arr[lp]
    kinds[first_sush] -= 1
    if not kinds[first_sush]: count -= 1
    lp += 1
    rp = (rp + 1) % n

    if not kinds[arr[rp]]: count += 1
    kinds[arr[rp]] += 1
    answer = max(answer, count) if kinds[c] else max(answer, count+1)

print(answer)

구간[a, b]에서 모든 종류의 보석을 살 수 있을 때부터 a+=1를 한다.(i.e. 구간의 범위가 좁아졌다.) 그리고 모든 범위의 보석을 살 수 있는지 본다. 살 수 있으면 살 수 없을 때 까지 계속 좁혀본다. 반대로, 좁혀진 범위의 구간에서 모든 종류의 보석을 살 수 없으면, b+=1을 하여 구간의 범위를 넓힌 후, 모든 종류의 보석을 살 수 있는지 확인한다. 이 과정을 a가 n 또는 b가 n이 될때까지 반복한다.(n은 보석개수)

위의 과정에서 얻은 구간 중 최소 구간을 구하면된다. 아이디어를 토대로 구현했는데 중간에 꼬여서 어떤 TC에서 a>b (아래의 코드에서는 lp > rp)일 때가 존재한다.(e.g.['ruby', 'ruby', 'ruby']) 정답처리 받았지만 그래도 내 코드보다는 위의 링크를 참고해서 푸는 것을 권장한다.

1. 코드

```python from collections import defaultdict

def solution(gems): size = len(gems) kinds = len(set(gems)) d = defaultdict(int) lp, rp = 0, 0 answer = [0, int(1e9)] count = 0 has_all_kind = False

while lp < size and rp < size:
    if not has_all_kind:
        if not d[gems[rp]]: count += 1
        d[gems[rp]] += 1

    if count == kinds:
        d[gems[lp]] -= 1
        if not d[gems[lp]]: count -= 1           
        answer = min(answer, [lp+1, rp+1], key=lambda x: abs(x[0]-x[1]))
        lp += 1
        has_all_kind = True
        continue

    has_all_kind = False
    rp += 1

return answer

정방향으로 순회하면서 어떻게하면 스택을 이용하여 문제를 해결할 수 있을까하며 30분동안 고민했지만 아이디어가 떠오르지 않았다. 그래서 역방향으로 순회해서 문제 해결을 시도했는데 됐다.
배열의 마지막 원소를 stack에 삽입하고 그 다음 원소부터 역방향으로 탐색을 시작한다. 현재 인덱스가 가리키는 배열의 원소와 stack에 저장된 마지막 원소를 비교한다. stack의 마지막 원소가 현재 인덱스가 가리키는 배열의 원소보다 클 때까지 pop연산을 한다. 그리고 그 원소(stack의 마지막 원소)를 다른 변수에 기록한다. 남아있는 stack이 없다면, -1를 기록한다. 이후, 현재 인덱스가 가리키는 배열의 원소 값을 stack에 삽입한다.
백준 예제 입력 1을 이용하여 설명하면, 입력으로 주어진 배열(arr),[3, 5, 2, 7]과 오큰수를 담는 배열, answer의 모든 원소가 -1로 초기화 되어있다.
우선, arr의 마지막 원소를 stack에 삽입하자. 따라서 stack = [7]이다. 그리고 arr의 마지막에서 2번째 원소부터 1번째 원소까지 역방향으로 탐색을 한다. arr[2]는 2이므로 stack의 마지막 원소인 7보다 작다. 따라서 answer[2]=7이다. 그리고 2를 stack에 삽입한다.
arr[1]은 5이다. 5는 stack의 마지막 원소인 2보다 크다. 따라서 stack에서 pop한다. pop연산 이후, stack의 마지막 원소는 7이다. 7은 5보다 크므로 answer[1]=7이다. 그리고 5를 stack에 삽입한다.
arr[0]은 3이다. 3은 stack의 마지막 원소인 5보다 작다. 따라서 answer[0]=5이다.

따라서 정답은 [5,7,7,-1]이다.

2. 코드

```python import sys

n = int(sys.stdin.readline().rstrip()) arr = list(map(int, sys.stdin.readline().rsplit()))

def solve(): if n == 1: return [-1] answer = [-1 for _ in range(n)] stack = [] stack.append(arr[-1]) for i in range(n-2, -1, -1): while stack and arr[i] >= stack[-1]: stack.pop() answer[i] = -1 if not stack else stack[-1] stack.append(arr[i])

return answer

answer = solve() for a in answer: print(a, end=' ')

문제의 요구사항을 지키면서 스택에 문자를 넣으면 메모리 초과가 발생한다. 예를들어 9(9(9(9(9(9(9(9(99999(1)))))))))가 입력으로 들어온다고 하자. 문자열 '1'이 99만 x 9^8개 찍힌다. 계산해보니 약 42조 5천억이다. 문제의 메모리 제한이 128MB이므로, 당연히 메모리 초과가 나온다. 사실 처음에 스택에 문자 넣고 제출하다 알게됐다.
따라서 K(Q)에서 Q는 문자열 개수를 스택에 넣는 방식으로 해결해야한다. 우선 K에 대한 스택과, Q에대한 스택을 만들었다. 각각 따로 사용하는 이유는 Q에 대한 스택에서는 문자열의 개수를 K에 대한 스택에서는 정수K를 넣을 것이기 때문이다. 그리고 입력으로 들어온 문자열에 대해 현재 인덱스와 바로 다음 인덱스가 가리키는 문자를 살펴보고 다음을 적용했다.

• 현재 인덱스가 숫자를 가리키고 다음 인덱스가 숫자를 가리키면, Q에 대한 스택의 마지막 값을 1 증가시킨다.
• 현재 인덱스가 숫자를 가리키고 다음 인덱스가 )를 가리키면 Q에 대한 스택의 마지막 값을 1 증가시킨다.
• 현재 인덱스가 숫자를 가리키고 다음 인덱스가 (를 가리키면, Q에 대한 스택에 0을 삽입하고, K에 대한 스택에 대해, 현재 인덱스가 가리키고 있는 숫자를 삽입한다.
• 현재 인덱스가 )를 가리키면, Q에 대한 스택에서 pop하여 얻은 값을 K에 대한 스택에서 pop하여 얻은 값과 곱한다. 그리고 Q에 대한 스택에서 원소를 갖고 있으면, pop하여 바로의 앞 결과와 더한후 Q에 대한 스택에 삽입한다.

(를 만날 때마다 Q에 대한 스택에 새로운 값, 0을 추가하여, 압축 해제에 적용될 대상을 구분했다. 그리고 )를 만날 때, K에 대한 스택의 마지막 값과 Q에 대한 스택의 마지막 값을 이용하여, 압축을 해제했다. 그리고 압축 해제에서 얻은 결과와 다음 압축 해제에 사용될 기존의 문자열의 길이를 더했다. 그래서 마지막 조건에 pop연산을 두 번했다. 다음 압축 해제에 적용될 기존의 문자열이 없다는 것은 1번째 pop연산 이후 Q에 대한 스택의 마지막 값이 0임을 의미한다.(e.g. 5(2(4)))

2. 코드

```python import sys

string = sys.stdin.readline().rstrip() rep = [] chs = [0] n = len(string) i = 0

while i < n-1: if string[i].isdigit() and string[i+1].isdigit(): chs[-1] += 1 elif string[i].isdigit() and string[i+1] == ')': chs[-1] += 1 elif string[i].isdigit() and string[i+1] == '(': chs.append(0) rep.append(int(string[i]))

elif string[i] == ')':
    x = chs.pop() * rep.pop()
    if chs: x = chs.pop() + x
    chs.append(x)

i += 1

if string[-1].isdigit(): chs[-1] += 1 else: x = chs.pop() * rep.pop() if chs: x = chs.pop() + x chs.append(x)

print(chs[0])

먼저 소수들을 에라토스테네스로 찾는다. 그리고 1번째 피연산자를 바꿔가며, 연속적으로 더해본다.(사용되는 피연산자들은 모두 소수) 그리고 그 결과가 N과 같다면 경우의 수를 하나 추가한다. 연속적으로 소수를 더하는 과정에서 N을 넘어버리게 된다면, 연산을 중단한 후, 1번째 피연산자의 바로 다음 소수를 1번째 피연산자로 지정한다.

1번째 피연산자가 N을 넘길 때까지 위의 과정을 반복한다.

2. 코드

import sys

n = int(sys.stdin.readline().rstrip())
table = [True for _ in range(n+1)]
for i in range(2): table[i] = False

for i in range(2, n+1):
    if table[i]:
        for k in range(i+i, n+1, i):
            table[k] = False

ln = 0
answer = 0
while True:
    while ln < n+1 and not table[ln]: ln += 1
    if ln == n+1: break
    ok = False
    total = 0

    for i in range(ln, n+1):
        if table[i]: total += i
        if total >= n:
            if total == n: ok = True
            break

    if ok: answer += 1
    ln += 1

print(answer)

문제에서 요구하는 것은 수열에서 두 수를 선택했을 때, 차이가 M이상이면서 제일 작은 경우를 구하는 것이다. 두 수를 선택하는데 있어, 수열의 형태는 중요하지 않다. 따라서 정렬 후, 문제 유형에서 제시된 것 처럼 투 포인터로 해결한다. 주의해야할 점은 같은 수를 고르는 경우도 있다는 것이다. 예를 들어, N=1일 때, 수를 2번 뽑는 경우이다. 1개의 정수를 2번 선택해서 차이를 구한다. 다시 말해, 수열을 배열(arr)로 표현할 때, 좌측 포인터(lp), 우측 포인터(rp)를 같은 인덱스에 두고, 동일한 곳을 가리키고 있는 수의 차이도 고려해야한다.(물론 결과는 0)
만약 차이가 M이상일 경우, 사전에 수열을 정렬시켰기 때문에, rp가 가리키는 곳 이후들은 고려하지 않아도 된다. 왜냐하면 우리가 원하는 것은 차이가 M이상이면서 제일 작은 경우를 구하는 것이기 때문이다. 따라서 lp가 다음 수를 가르키게하고, lp가 가르킨 곳을 rp도 가르키게한다.
만약 차이가 M미만일 경우, rp가 다음 수를 가르키게한다. 차이가 M이상이 될 때까지 반복하고 rp가 N이 되는 순간, lp가 다음 수를 가르키게하고 rp도 lp가 가르킨 곳을 가르킨다.
위의 과정들을 lp가 N이 될 때까지 반복한다. 그리고 차이가 M이상이면서 그 차이가 가장 적은 것을 선택하면된다.

2. 코드

```python import sys

n, m = map(int, sys.stdin.readline().rsplit()) arr = [] for _ in range(n): arr.append(int(sys.stdin.readline().rstrip()))

arr.sort() lp, rp = 0, 0 answer = int(2e9)

while lp < n: diff = abs(arr[lp]-arr[rp]) if diff >= m: answer = min(answer, diff) if diff == m : break lp += 1 rp = lp continue

rp += 1
if rp == n:
    lp += 1
    rp = lp

print(answer)

회전 초밥에서 연속적으로 k개의 초밥을 선택하고, 각 초밥 번호를 집합에 넣는다. 집합의 특성상 중복되는 번호는 없다. 쿠폰 번호가 집합에 속하지 않는다면, 집합 크기 + 1 종류의 초밥을 먹은것을 의미한다. 쿠폰 번호가 집합에 속해있다면, 집합 크기종류의 초밥을 먹은 것을 의미한다.
초밥을 처음 선택할 시작점을 바꿔가며 연속적으로 k개의 초밥을 선택해서, 먹은 초밥의 종류 중 가장 많은 종류를 먹은 초밥을 구하면된다. 회전 초밥을 배열로 표현할 경우, 인덱스 처리에 주의하자. 다시 말해, 미리 인덱스에 %n연산을 적용해서 배열에 접근하자.

2. 코드

```python import sys

n, d, k, c = map(int, sys.stdin.readline().rsplit()) arr = [int(sys.stdin.readline().rstrip()) for _ in range(n)] lp, rp = 0, 0 answer = 0

while lp != n: rp = lp + k case = set() addable = True for i in range(lp, rp): i %= n case.add(arr[i]) if arr[i] == c: addable = False

cnt = len(case)
if addable: cnt += 1
answer = max(answer, cnt)
lp += 1

print(answer)

우리가 찾아야하는 답은 승률이 변하기 위한 최소 게임 판 수 이다. 따라서 최소 게임 판 수를 이분탐색으로 찾아본다.
형택이가 앞으로 하는 게임은 전부 이기는 게임이다. 따라서 승률이 변하는 것은 승률이 오른다는 것을 의미한다. 반면, 아무리 게임을 많이 해도 승률이 전혀 오르지 않을 경우(-1를 출력하게되는 경우)를 이분탐색의 관점에서 생각해보자. 이는 이분 탐색을 진행한 결과 left 값이 초기에 설정된 right 값보다 크다는 것을 의미한다.
초기 설정할 left, right의 값을 구해야한다. left는 최소 1판의 게임을 하므로 1이라는 것을 알고 있다. 근데 right는 어떻게 구할까. 사실 나는 이 문제에서 찾지 못해서 최대 할 수 있는 게임판 수를 10억으로 임의 설정했다. 1번째 문단을 고려할 때, left가 10억이 넘어가버리면 승률를 올릴 수 없다고 판단하여 -1를 출력하게된다.
이번에는 승률이 오를 수 있는 상황을 생각해보자. 추가적인 게임 판수를 진행했음에도 승률이 오르지 않는다면 게임 판 수를 늘리면된다. 다시 말해 left = mid + 1이다. 반대로 승률이 올랐다면, 판 수를 한번 줄여보자. 왜냐하면, 우리가 원하는 것은 승률이 변할 수 있는 최소 판 수이기 때문이다. 이 과정을 이분탐색으로 구현한다.

2. 코드

import sys

x, y = map(int, sys.stdin.readline().rsplit())

INF = int(1e9)
left = 1
right = INF
win_rate = y*100 // x 
answer = INF

while left <= right:
    mid = (left+right) // 2
    games = x + mid
    wins = y + mid
    k = wins*100 // games

    if k == win_rate: left = mid + 1
    else:
        answer = min(answer, mid)
        right = mid - 1

if left > INF: print(-1)
else: print(answer)

1. 아이디어

게임보드에서 빈칸들을 찾고 테이블에서 존재하는 모든 퍼즐조각을 찾는다. 각 빈칸에 대해 모든 퍼즐조각을 대입해본다. 만약 매칭이되면, 게임보드에서 퍼즐조각을 채우고, 테이블에서 해당 퍼즐조각을 지운다. 그리고 변수, answer에 해당 퍼즐조각 개수만큼 더하고 다음 게임보드의 빈칸으로 넘어간다. 만약 알맞는 퍼즐조각이 하나도 없다면, 테이블을 90도 회전하고 다시 퍼즐조각을 빈칸에 대입하여 매칭이되는지 확인해본다. 회전을 계속하여 동일한 테이블로 왔지만, 매칭되는 퍼즐조각을 찾지 못했다면 다음 게임보드의 빈칸으로 넘어간다
모든 빈칸에 대해 위의 방식을 적용하면 된다.

게임보드에서 빈칸을 찾아 저장하는 것은 bfs와 딕셔너리로 구현했다. 게임보드에서 처음보는 빈칸일 경우, 해당 좌표를 딕셔너리의 값으로 리스트에 추가하고 인접한 빈칸의 개수를 딕셔너리의 키로 설정했다. 테이블에 존재하는 모든 퍼즐조각도 같은 방식으로 구현했다.
퍼즐조각 매칭하는 것도 bfs로 구현했다. 만약 게임보드의 빈칸과 테이블의 퍼즐조각이 매칭이 된다면, 움직이는 방향이 동일하기 때문에 bfs로 구현할 수 있다.
매칭이 됐을 때, 테이블에서 퍼즐조각을 지우는 것도, 게임보드에서 퍼즐조각을 채우는 것도 전부 bfs로 구현했다. 각각의 함수에 대해 bfs를 별도로 구현했기 때문에 코드가 너무 길어졌다.

2. 코드

```python from collections import deque, defaultdict

r, c = 0, 0 d = ((0,1), (1,0), (-1,0), (0,-1)) board_visited = [] table_visited = [] tdict = defaultdict(list) gdict = defaultdict(list)

def rotate(table): global r, c copy = [[-1 for _ in range(c)] for _ in range(r)] q = deque()

for i in range(r):
    for j in range(c):
        q.append(table[i][j])

for j in range(c-1, -1, -1):
    for i in range(r):
        copy[i][j] = q.popleft()

return copy

def isin(y, x): global r, c if -1<y<r and -1<x<c: return True return False

def find_empty_spaces(game_board, sy, sx): global board_visited, gdict q = deque() q.append((sy, sx)) cnt = 1

while q:
    y, x = q.popleft()
    for dy, dx in d:
        ny = y + dy
        nx = x + dx

        if not isin(ny, nx): continue
        if not board_visited[ny][nx]:
            board_visited[ny][nx] = True
            if game_board[ny][nx] == 0:
                cnt += 1
                q.append((ny, nx))

gdict[cnt].append((sy, sx))

def _find_puzzles(table, sy, sx): global table_visited, tdict q = deque() q.append((sy, sx)) cnt = 1

while q:
    y, x = q.popleft()
    for dy, dx in d:
        ny = y + dy
        nx = x + dx
        if not isin(ny, nx): continue
        if not table_visited[ny][nx]:
            table_visited[ny][nx] = True
            if table[ny][nx] == 1:
                cnt += 1
                q.append((ny, nx))

tdict[cnt].append((sy, sx))

def find_puzzles(table): global table_visited, r, c, tdict tdict = defaultdict(list) table_visited = [[False for _ in range(c)] for _ in range(r)]

for i in range(r):
    for j in range(c):
        if not table_visited[i][j]:
            table_visited[i][j] = True
            if table[i][j] == 1: _find_puzzles(table, i, j)

def match_puzzle(gy, gx, ty, tx, table, game_board): global board_visited, table_visited, r, c board_visited = [[False for _ in range(c)] for _ in range(r)] table_visited = [[False for _ in range(c)] for _ in range(r)] board_visited[gy][gx] = True table_visited[ty][tx] = True match_count = 1 q = deque() q.append((gy, gx, ty, tx))

while q:
    gy, gx, ty, tx = q.popleft()
    for dy, dx in d:
        ngy = gy + dy
        ngx = gx + dx
        nty = ty + dy
        ntx = tx + dx
        if not isin(ngy, ngx) or not isin(nty, ntx): continue
        if board_visited[ngy][ngx] or table_visited[nty][ntx]: continue
        board_visited[ngy][ngx] = True
        table_visited[nty][ntx] = True
        if game_board[ngy][ngx] == 1 or table[nty][ntx] == 0: continue
        match_count += 1
        q.append((ngy, ngx, nty, ntx))

return match_count

def remove_puzzle(table, sy, sx): global table_visited, r, c table_visited = [[False for _ in range(c)] for _ in range(r)] table[sy][sx] = 0 q = deque() q.append((sy, sx)) table_visited[sy][sx] = True while q: y, x = q.popleft() for dy, dx in d: ny = y + dy nx = x + dx if not isin(ny, nx): continue if not table_visited[ny][nx]: table_visited[ny][nx] = True if table[ny][nx] == 1: table[ny][nx] = 0 q.append((ny, nx))

return table

def fill_puzzle(game_board, sy, sx): global board_visited, r, c board_visited = [[False for _ in range(c)] for _ in range(r)] q = deque() q.append((sy, sx)) board_visited[sy][sx] = True game_board[sy][sx] = 1

while q:
    y, x = q.popleft()
    for dy, dx in d:
        ny = y + dy
        nx = x + dx
        if not isin(ny, nx): continue
        if not board_visited[ny][nx]:
            board_visited[ny][nx] = True
            if game_board[ny][nx] == 0:
                game_board[ny][nx] = 1
                q.append((ny, nx))

return game_board

def solution(game_board, table): global table_visited, board_visited, tables, r, c global gdict, tdict r, c = len(table), len(table[0]) table_visited = [[False for _ in range(c)] for _ in range(r)] board_visited = [[False for _ in range(c)] for _ in range(r)] answer = 0

for i in range(r):
    for j in range(c):
        if not board_visited[i][j]:
            board_visited[i][j] = True
            if game_board[i][j] == 0: find_empty_spaces(game_board, i, j)

for i in range(1, 7):
    if not gdict[i]: continue
    while gdict[i]:
        gy, gx = gdict[i].pop()
        ok = False
        ry, rx = -1, -1
        for _ in range(4):
            table = rotate(table)
            find_puzzles(table)

            for ty, tx in tdict[i]:
                count = match_puzzle(gy, gx, ty, tx, table, game_board)
                if count == i:
                    answer += i
                    ok = True
                    ry, rx = ty, tx
                    break

            if ok: break

        if ok:
            table = remove_puzzle(table, ry, rx)
            game_board = fill_puzzle(game_board, gy, gx)


return answer