첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

이 문제는 시뮬레이션과 BFS를 결합한 문제이다. 매일 국경선이 열리는 나라들을 찾아 연합을 만들고, 인구를 재분배하는 과정을 반복해야 한다.

인구 이동이 일어나는 하루는 다음과 같은 과정을 거친다:

1. 연합 찾기: BFS를 사용하여 국경선이 열리는 나라들의 연합을 찾는다.
2. 인구 재분배: 각 연합의 평균 인구수를 계산하고 재분배한다.
3. 종료 조건 확인: 어떤 연합도 만들어지지 않으면 인구 이동 종료.

1. 연합 찾기 (open 함수)

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

floor = [list(input()) for _ in range(N)]

def search_tiles(start, visited, tile_shape):
    # 타일 모양에 따라 탐색 방향 설정
    if tile_shape == '-':
        dy, dx = 0, 1
    else:
        dy, dx = 1, 0

    q = deque([start])
    while q:
        y, x = q.popleft()

        ny, nx = y + dy, x + dx

        # 범위 벗어났을 경우
        if not (0 <= ny < N) or not (0 <= nx < M):
            return 1
        # 이미 방문했을 경우
        if visited[ny][nx]:
            return 1
        # 타일 모양이 다를 경우
        if floor[ny][nx] != tile_shape:
            return 1

        q.append((ny, nx))
        visited[ny][nx] = True

visited = [[False] * M for _ in range(N)]
tile_cnt = 0

for y in range(N):
    for x in range(M):
        if visited[y][x]:
            continue
        tile_cnt += search_tiles((y, x), visited, floor[y][x])

print(tile_cnt)

• len_limit = min(N - 1, M - 1): 가능한 최대 정사각형의 한 변 길이 (인덱스 차이)
• for k in range(len_limit, -1, -1): 큰 정사각형부터 확인
• for x in range(M - k): 정사각형의 시작 x 좌표 (x + k가 범위를 벗어나지 않도록)
• for y in range(N - k): 정사각형의 시작 y 좌표 (y + k가 범위를 벗어나지 않도록)
• 네 꼭짓점 비교: rectangle[y][x] (좌상), rectangle[y + k][x] (좌하), rectangle[y][x + k] (우상), rectangle[y + k][x + k] (우하)
• break-else 패턴: 조건을 만족하는 정사각형을 찾으면 모든 반복문을 빠져나감

최악의 경우 모든 가능한 정사각형을 확인해야 하므로 시간 복잡도는 O(N × M × min(N, M))이다.

N, M ≤ 50이므로 최악의 경우에도 50 × 50 × 50 = 125,000번의 연산으로 충분히 시간 내에 해결할 수 있다.

max_h = 0
pillar_list = [0] * 1001

max_loc = 0
for _ in range(N):
    loc, h = map(int, input().split())
    max_h = max(max_h, h)
    max_loc = max(max_loc, loc)
    pillar_list[loc] = h

# 왼쪽에서 시작
i_l = -1
cur = 0
ans = 0
while cur < max_h:
    i_l += 1
    cur = max(cur, pillar_list[i_l])
    ans += cur

# 오른쪽에서 시작
i_r = max_loc + 1
cur = 0
while cur < max_h:
    i_r -= 1
    cur = max(cur, pillar_list[i_r])
    ans += cur

if i_r == i_l:
    ans -= max_h
else:
    ans += max_h * (i_r - i_l - 1)

print(ans)

word = input().upper()

counter = defaultdict(int)

max_cnt = 0
max_alpha = ''
same_chk = False

for a in word:
    counter[a] += 1
    if counter[a] > max_cnt:
        max_cnt = counter[a]
        max_alpha = a
        same_chk = False
    elif counter[a] == max_cnt:
        same_chk = True

if same_chk:
    print('?')
else:
    print(max_alpha)

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 ’.’, ’#’, ‘O’, ‘R’, ‘B’ 로 이루어져 있다. ’.’은 빈 칸을 의미하고, ’#‘은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, ‘O’는 구멍의 위치를 의미한다. ‘R’은 빨간 구슬의 위치, ‘B’는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 ’#‘이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

맵을 BFS로 탐색하면서 시뮬레이션 하는 문제이다.

처음 시도한 방식은 정말 단순하게 모두 다 구현하는 것으로 맵 리스트 자체에서 구슬들을 실제로 움직이는 것까지 구현하였다.

위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C뿐이므로 이들은 모두 2등이 된다. 그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 5등이 된다. 위 경우에 3등과 4등은 존재하지 않는다. 여러분은 학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.

첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 나타난다.

여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다.

merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       # q는 p, r의 중간 지점
        merge_sort(A, p, q);      # 전반부 정렬
        merge_sort(A, q + 1, r);  # 후반부 정렬
        merge(A, p, q, r);        # 병합
    }
}

# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  # 왼쪽 배열 부분이 남은 경우
        tmp[t++] <- A[i++];
    while (j ≤ r)  # 오른쪽 배열 부분이 남은 경우
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  # 결과를 A[p..r]에 저장
        A[i++] <- tmp[t++];
}

nums = {1 : [1],
        2 : [2, 4, 8, 6],
        3 : [3, 9, 7, 1],
        4 : [4, 6],
        5 : [5],
        6 : [6],
        7 : [7, 9, 3, 1],
        8 : [8, 4, 2, 6],
        9 : [9, 1]}

for _ in range(n):
    a, b = map(int, input().split())
    # a의 1의 자리수를 구한다 -> 4
		one = a % 10

		# 1의 자리에 나올 수 있는 값들을 가져온다 -> nums[4] -> [4, 6]
		# 이 중에서 b번째 값을 취한다. 4, 6, 4, 6, 4, 6 -> 6
    print(nums[one][(b - 1) % len(nums[one])])

단 a의 1의 자리가 0일 경우 무조건 제곱한 수의 1의 자리도 0이므로 10번 컴퓨터가 처리하게 된다.