17140_이차원 배열과 연산 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 4)
• 링크 : 17140번: 이차원 배열과 연산

1. 기록

• 22/04/21 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>>

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
1 2 2
1 2 1
2 1 3
3 3 3

- 예제 출력 1 -
0

- 예제 입력 2 -
1 2 1
1 2 1
2 1 3
3 3 3

- 예제 출력 2 -
1

- 예제 입력 3 -
1 2 3
1 2 1
2 1 3
3 3 3

- 예제 출력 3 -
2

- 예제 입력 4 -
1 2 4
1 2 1
2 1 3
3 3 3

- 예제 출력 4 -
52

- 예제 입력 5 -
1 2 5
1 2 1
2 1 3
3 3 3

- 예제 출력 5 -
-1

- 예제 입력 6 -
3 3 3
1 1 1
1 1 1
1 1 1

- 예제 출력 6 -
2

(3) 코드

from collections import Counter
from functools import reduce


## R 연산
def R(array):
    mx = 0  # 가장 긴 리스트의 길이
    pprint(array)
    for i in range(len(array)):

        X = Counter(array[i])


        del X[0]  # 수를 정렬할 때, 0은 제외
        X = list(X.items())
        X.sort(key=lambda x: (x[1], x[0]))
        if len(X) > 50: X = X[:50]  # 크기가 100을 넘기면 안됨.
        array[i] = reduce(lambda x, y: list(x) + list(y), X[1:], list(X[0]))
        mx = max(mx, len(array[i]))

    ## 가장 긴 리스트에 맞춰, 0을 추가한다.
    for i in range(len(array)):
        if len(array[i]) < mx:
            array[i].extend([0] * (mx - len(array[i])))


def main():
    r, c, k = map(int, input().split())
    r, c = r - 1, c - 1

    graph = [list(map(int, input().split())) for _ in range(3)]
    time = 0  # 시간
    if r < len(graph) and c < len(graph[0]):
        if graph[r][c] == k:
            return time

    while True:
        if len(graph) >= len(graph[0]):  # 행의 개수 >= 열의 개수, R연산
            R(graph)  # R 연산

        else:  # 행의 개수 < 열의 개수, C연산
            graph = list(map(list, zip(*graph)))  # 트랜스포즈
            R(graph)  # R 연산
            graph = list(map(list, zip(*graph)))  # 트랜스포즈
        time += 1

        if time > 100:
            return -1

        if r < len(graph) and c < len(graph[0]):
            if graph[r][c] == k:
                return time


print(main())

(4) 정리

문제 설명에서 R연산, C연산에 대해서 '행에 대해서 or 열에대해서 정렬을 수행한다.' 라고 되어있어서
정렬을 수행한다는게 무슨말인지 몰랐다.
정렬을 수행한다. -> 문제 설명에 있는 로직을 행에 대해서 or 열에 대해서 수행한다는 말이다.
로직은 특정 숫자를 카운트하고 그에 대한 결과를 정렬하는건데 단순히 정렬이라고만해서 문제 이해하는데 한참 걸렸다.

문제를 푸는데 있어서 파이썬의 각 함수들의 사용법 이해도가 중요하다고 느꼈습니다.

위의 풀이에서 사용된 함수는 zip, Conter, items, reduce, extend 등이 있습니다.

특히 트랜스포즈하는 코드는 미리 알고있지 않으면 생각해내서 구현하기 힘든 코드라고 생각해서 암기해야할 것 같습니다.

graph = list(map(list, zip(*graph)))  # 트랜스포즈

reduce 와 extend 도 위 문제 풀이를 찾으면서 처음 본 함수였습니다.
reduce 함수는 '감소시킨다'는 의미의 쓰임은 전혀없고 '누적'의 의미로 쓰이는 함수입니다.★

(5) 참고

파이썬 asterisk(*) 사용 용도
파이썬의 zip() 내장 함수로 데이터 엮기
coolections모듈의 Counter함수
Key, Value 쌍 얻기(items)
파이썬 reduce 함수 사용법
파이썬 extend 함수

21609_상어 중학교 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 2)
• 링크 : 21609번: 상어 중학교

1. 기록

• 22/04/21 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 가장 큰 블록 그룹을 만들기 위해 dfs를 돌린다.

>> 그러한 블록 그룹이 여러개라면
>> 1. 무지개 블록의 수가 가장 많은 블록 그룹

>> 그러한 블록 그룹이 여러개라면
>> 2. 기준 블록의 행이 가장 큰 것을,

>> 그러한 블록 그룹이 여러개라면
>> 3. 열이 가장 큰 것을 찾는다.

>> BFS를 돌렸을 때 해당 색깔블록이 뭐지 카운트해준다.(color)
>> 무지개 블록의 갯수도 카운트해준다. (rainbow)
>> 검정 블록은 카운트해주지 않는다. (black)
>> 최대의 색깔블록 + 무지개블록 칸을 없애주고 점수를 매겨준다. (total_block)
>> 최대의 total_block 을 계속 생신해주면서 최댓값을 찾는다.

>> 중력 작용 (칸을 벗어나기 직전까지 또는 이동하려는 칸에 다른 블록이 있을때 까지)
>> 검은색 블록 -1 은 움직이지 않는다.
>> dx = [1]
>> dy = [0]

>> 반시계방향으로 회전
>> 행이 열로 바뀜
>> 열이 일정하면서 최대인경우 최소 행으로 바뀜
>> 열이 일정하면서 최소인경우 최대 행으로 바뀜


2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
5 3
2 2 -1 3 1
3 3 2 0 -1
0 0 0 1 2
-1 3 1 3 2
0 3 2 2 1

- 예제 출력 1 -
77

- 예제 입력 2 -
6 4
2 3 1 0 -1 2
2 -1 4 1 3 3
3 0 4 2 2 1
-1 4 -1 2 3 4
3 -1 4 2 0 3
1 2 2 2 2 1

- 예제 출력 2 -
125

- 예제 입력 3 -
4 3
1 1 1 3
3 2 3 3
1 2 -1 3
-1 -1 1 1

- 예제 출력 3 -
33

(3) 코드

from collections import deque
from pprint import pprint

# 인접 블록 찾기 -> 블록 크기, 무지개크기, 블록좌표 리턴
def bfs(x, y, color):
    q = deque()
    q.append([x, y])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    block_cnt, rainbow_cnt = 1, 0  # 블록개수, 무지개블록 개수
    blocks, rainbows = [[x, y]], []  # 블록좌표 넣을 리스트, 무지개좌표 넣을 리스트

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

            # 범위 안이면서 방문 안한 일반 블록인 경우
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and a[nx][ny] == color:
                visited[nx][ny] = 1
                q.append([nx, ny])
                block_cnt += 1
                blocks.append([nx, ny])

            # 범위 안이면서 방문 안한 무지개 블록인 경우
            elif 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and a[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append([nx, ny])
                block_cnt += 1
                rainbow_cnt += 1
                rainbows.append([nx, ny])

    # 무지개블록은 방문 다시 해제
    for x, y in rainbows:
        visited[x][y] = 0

    return [block_cnt, rainbow_cnt, blocks + rainbows]


# 블록 제거 함수
def remove(block):
    for x, y in block:
        a[x][y] = -2


# 중력 함수
def gravity(a):
    for i in range(N - 2, -1, -1):  # 밑에서 부터 체크
        for j in range(N):
            if a[i][j] > -1:  # -1이 아니면 아래로 다운
                r = i
                while True:
                    if 0 <= r + 1 < N and a[r + 1][j] == -2:  # 다음행이 인덱스 범위 안이면서 -2이면 아래로 다운
                        a[r + 1][j] = a[r][j]
                        a[r][j] = -2
                        r += 1
                    else:
                        break


# 반시계 회전 함수
def rot90(a):
    new_a = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            new_a[N - 1 - j][i] = a[i][j]
    return new_a


# 0. 메인코드
N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]

# N = int(5)
# M = int(3)
# a = [[2, 2, -1, 3, 1],
#  [3, 3, 2, 0, -1],
#  [0, 0, 0, 1, 2],
#  [-1, 3, 1, 3, 2],
#  [0, 3, 2, 2, 1]]

score = 0  # 점수

# 1. 오토플레이-> while {2. 크기 가장 큰 블록 찾기 3. 블록제거+점수더하기 4. 중력 5. 90회전 6. 중력}
while True:
    # 2. 크기 가장 큰 블록 찾기
    visited = [[0] * N for _ in range(N)]  # 방문체크
    blocks = []  # 가능한 블록 그룹들 넣을 리스트
    for i in range(N):
        for j in range(N):
            if a[i][j] > 0 and not visited[i][j]:  # 일반블록이면서 방문 안했으면
                visited[i][j] = 1  # 방문
                block_info = bfs(i, j, a[i][j])  # 인접한 블록 찾기
                pprint(block_info)
                # block_info = [블록크기, 무지개블록 개수, 블록좌표]
                if block_info[0] >= 2:
                    blocks.append(block_info)
    blocks.sort(reverse=True)

    # 3. 블록제거+점수더하기
    if not blocks:
        break
    remove(blocks[0][2])
    score += blocks[0][0] ** 2

    # 4. 중력
    gravity(a)

    # 5. 90회전
    a = rot90(a)

    # 6. 중력
    gravity(a)

print(score)

(4) 정리

시험에서 이렇게 코드 짤 수 있을지 의문이다.

내가 생각하는 포인트

1. 이미 visited된 곳은 블록 카운트 시도하지 않는 것
2. rainbow 블록은 visited 초기화
3. 블록 좌표들을 하나하나 다 append 해서 점수를 매길때 해당 좌표 블록은 삭제하는 것 (코드에서는 -2라는 값을 할당함)
4. 중력함수 짜는 것 -> 이동하려는 칸이 비어있으면 계속 내려오게끔 코드가 짜여져 있음
5. 90도 반시계방향 회전하는 코드 어떻게 바로 생각해 내는지

(5) 참고

참고 풀이

16236_아기 상어 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 3)
• 링크 : 16236번: 아기 상어

1. 기록

• 22/04/20 (수)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 물고기 위치 및 상어를 이차원 배열로 담는다.
>> 상어의 위치에서 bfs 돌린다. -> 이때 해당 물고기를 찾으면서 시간이 최소인 경우에 그 물고기를 먹는다. 또한 먹은 물고기 좌표를 따로 queue에 담아둔다.
>> 시간이 걸린 물고기가 2개 이상인 경우 각 물고기 좌표를 비교해서 더 작은쪽을 먹고 해당 물고기 좌표를 따로 queue에 담아둔다.

>> 다시 상어의 시작 위치는 queue에 담긴 좌표가 될 것이다.
>> bfs를 다시 돌린다.

>> 어떤 단위 등으로 함수를 나눌 것인지 잘 판단하자 ★

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3
0 0 0
0 0 0
0 9 0

- 예제 출력 1 -
0

- 예제 입력 2 -
3
0 0 1
0 0 0
0 9 0

- 예제 출력 2 -
3

- 예제 입력 3 -
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4

- 예제 출력 3 -
14

- 예제 입력 4 -
6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

- 예제 출력 4 -
60

- 예제 입력 5 -
6
6 0 6 0 6 1
0 0 0 0 0 2
2 3 4 5 6 6
0 0 0 0 0 2
0 2 0 0 0 0
3 9 3 0 0 1

- 예제 출력 5 -
48

(3) 코드

# 시간초과

from collections import deque

n = int(input())
graph = list(list(map(int, input().split())) for _ in range(n))

# 상어 이동
def move(q, graph, time, f_graph, size):
    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]
    visited = [[0]*n for _ in range(n)]

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

        # x,y가 찾는 물고기 좌표라면
        if graph[x][y] < size and graph[x][y] > 0:
            f_graph.append((x, y, visited[x][y]))

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 안에 있고 size가 같거나 작으면
            if 0<=nx<n and 0<=ny<n:
                if graph[nx][ny] <= size and visited[nx][ny] == 0:
                    visited[nx][ny] += visited[x][y] + 1
                    q.append((nx,ny))

        if not q:
            return f_graph


q = deque()
time = 0
total_time = 0
size = 2
feed = 0

while 1:

    # 0. 상어 좌표를 찾는다.
    for x1 in range(n):
        for y1 in range(n):
            if graph[x1][y1] == 9:
                s_x = x1
                s_y = y1
                break

    q.append((s_x, s_y))

    # 1. 상어 이동
    f_graph = []
    f_graph = move(q, graph, time, f_graph, size)

    # 2. 찾는 물고기 좌표 비교
    if len(f_graph) >= 1:
        graph[s_x][s_y] = 0

        # 시간, x좌표, y좌표 순서의 오름차순으로 정렬 ★
        f_graph.sort(key=lambda x : (x[2], x[0], x[1]))

        # print(f"f_graph 입니다. {f_graph}")
        f_x, f_y, time = f_graph[0]
        f_graph = []

        graph[f_x][f_y] = 9

        feed += 1

        total_time += time
        time = 0
        if size == feed:
            size += 1
            feed = 0

    elif len(f_graph) == 0:
        print(total_time)
        break

from collections import deque

n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]

# n = int(6)
# arr = [[6, 0, 6, 0, 6, 1],
#  [0, 0, 0, 0, 0, 2],
#  [2, 3, 4, 5, 6, 6],
#  [0, 0, 0, 0, 0, 2],
#  [0, 2, 0, 0, 0, 0],
#  [3, 9, 3, 0, 0, 1]]

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

sx, sy = 0, 0

# 상어의 위치를 찾는다.
for i in range(n):
    for j in range(n):
        if arr[i][j] == 9:

            # 상어위치를 0으로 만들어준다.
            arr[i][j] = 0
            sx, sy = i, j
            break

size = 2
move_num = 0
feed = 0

while True:
    q = deque()
    q.append((sx, sy, 0))
    visited = [[False] * n for _ in range(n)]
    flag = 1e9
    fish = []

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

        # count가 flag(먹이를 찾은 지점까지의 거리)보다 커지는 경우
        # 더 이상 찾을 필요가 없으므로 break 한다.
        if count > flag:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위를 벗어나는 경우 못지나감
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue

            # size 보다 큰 경우 못지나감 방문한경우 못 지나감
            if arr[nx][ny] > size or visited[nx][ny]:
                continue

            # size보다 작은 물고기가 있는 경우
            if arr[nx][ny] != 0 and arr[nx][ny] < size:
                fish.append((nx, ny, count + 1))
                print(f"fish 를 먹었습니다 : {fish}")
                flag = count
                print(f"count 입니다 {count}")
            visited[nx][ny] = True

            # 내가 생각하는 핵심 부분★
            q.append((nx, ny, count + 1))

    # 먹이를 먹은 경우(같은 거리)
    if len(fish) > 0:
        fish.sort()
        print(f"먹은 fish입니다 : {fish}")
        x, y, move = fish[0][0], fish[0][1], fish[0][2]
        move_num += move
        feed += 1

        # 먹은 fish자리는 0으로 바꿔준다.
        arr[x][y] = 0

        if feed == size:
            size += 1
            feed = 0

        # 상어의 위치를 바꿔준다. ★
        sx, sy = x, y
    else:
        break

print(move_num)

(4) 정리

생각하는 로직은 맞았는데 생각한 로직대로 구현을 못했다..
문제 구현하고 답안보고 이해하는데까지 3시간걸렸다.

(5) 참고

참고 풀이

21608_상어 초등학교 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (silver 1)
• 링크 : 21608번: 상어 초등학교

1. 기록

• 22/04/20 (수)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 해당 index(학생번호)가 좋아하는 학생이 자리에 있는지를 찾는다.
>> 그러한 자리가 없으면 인접한 칸이 많은 빈 칸을 찾아 들어간다.
>> 그러한 자리 중 인접한 빈칸이 많은 자리로 들어가고
>> 그러한 자리 중 인접한 빈칸의 갯수 까지 같으면 행 번호, 열 번호가 작은 칸으로 들어간다.

2. 시간복잡도
>>

3. 자료구조
>> 2차원 리스트로 해결되는건지..?
>> 3차원 리스트를 써야되는건지..?

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

import sys
from collections import defaultdict

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

n = int(input())

graph = [[0]*n for _ in range(n)]
likedict = defaultdict(list)
result = 0

for _ in range(n*n):

    # 한 줄씩 입력하고 그에 대한 자리를 잡는다.
    # 각 입력에대해 max_like 와 max_empty 를 세어본다.
    info = list(map(int, input().split()))
    likedict[info[0]] = info[1:]

    max_x = 0
    max_y = 0
    max_like = -1
    max_empty = -1

    print(f"graph 입니다. : {graph}")

    for x in range(n):
        for y in range(n):

            # 자리가 비어있는 경우
            if graph[x][y] == 0:
                likecnt = 0
                emptycnt = 0
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<n and 0<=ny<n:
                        # 그 자리 주변에 호감가는 학생이 있는지 확인한다.
                        if graph[nx][ny] in info:
                            likecnt += 1

                        # 그 자리 주변에 비어있는 자리가 있는지 확인한다.
                        if graph[nx][ny] == 0:
                            emptycnt += 1

                # 좋아하는 학생이 인접한 칸에 가장 많은 칸 또는 like갯수는 max_like와 같으면서 최대 empty갯수인 경우
                # print(f"max_like 입니다. {max_like}")
                # print(f"likecnt 입니다. {likecnt}")
                # print(f"max_empty 입니다. {max_empty}")
                # print(f"emptycnt 입니다. {emptycnt}")

                # 주변의 호감학생수가 최대로 갱신되는 경우 또는 1을 만족하는 칸이 여러 칸인 경우(호감학생수는 그대로인데 빈칸 갯수가 최대로 갱신되는 경우)
                if max_like < likecnt or (max_like == likecnt and max_empty < emptycnt):
                    max_x = x
                    max_y = y
                    max_like = likecnt
                    max_empty = emptycnt

    # 그러한 곳에 자리를 잡는다.
    graph[max_x][max_y] = info[0]

for x in range(n):
    for y in range(n):
        cnt = 0
        print(f"likedict입니다 : {likedict}")
        like = likedict[graph[x][y]]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<n:
                # 인접한 곳에 호감학생이 있는 경우
                if graph[nx][ny] in like:
                    cnt += 1

        # cnt에 해당하는 점수를 매긴다.
        if cnt != 0:
            result += 10 ** (cnt-1)

print(result)

(4) 정리

어떻게 like수와 empty를 체크하면서 작성해야하는지 정리가 안되서 정답코드를 봤다.
defaultdict() 등 알고 있는 함수지만 써먹지 않고 있는 것들을 잘 써먹을 수 있도록 연습좀 해놔야겠다.★★

(5) 참고

참고 풀이
defaultdict() 활용법

14889_스타트와 링크 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (silver 2)
• 링크 : 14889번: 스타트와 링크

1. 기록

• 22/04/20 (수)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 팀원을 이룰 수 있는 모든 경우의 수를 구해야한다.
>> 그리고 표에 주어진 능력치를 적용시켜 팀별로 그 합을 구하고 합의 차이가 가장 작은 경우를 찾는다.
>> 조합의 수를 구해야 함. 

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

from itertools import combinations

n = int(input())
nums = list(i for i in range(n))
graph = list(list(map(int,input().split())) for _ in range(n))

combis = list(combinations(nums, n//2))

min = 10000000
answer_list = []
for comb in combis:
    start = set(comb)
    link = set(nums) - start

    start = list(start)
    link = list(link)

    start_comb = list(combinations(start, 2))
    link_comb = list(combinations(link, 2))

    # print(f"start 입니다. {start}")
    # print(f"link 입니다. {link}")

    case1 = 0
    case2 = 0

    for x1, y1 in start_comb:
        case1 += graph[x1][y1] + graph[y1][x1]

    for x2, y2 in link_comb:
        case2 += graph[x2][y2] + graph[y2][x2]

    if min > abs(case1 - case2):
        min = abs(case1 - case2)
        # print(f"case1 입니다. {case1}")
        # print(f"case2 입니다. {case2}")

print(min)

(4) 정리

튜플 형태의 comb에 반대되는 조합을 어떻게 구해야하나 모르겠어서 이 부분만 찾아봤습니다.
comb를 set형태로 바꾸고 전체 숫자 set(nums)에서 해당 set(comb)를 빼면 나머지숫자로 조합된 comb를 구할 수 있었습니다.

(5) 참고

참고 풀이

13458_시험 감독 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 기출 (bronze 2)
• 링크 : 13458번: 시험 감독

1. 기록

• 22/04/20 (수)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 각 시험장에 있는 사람들에서 b를 빼고 그 결과를 c로 계속나눠서 그 몫을 구한다.
>> c로 나눴을 때 나머지가 있는 경우 몫에 + 1 해주고 나머지가 없는경우 그 몫만 가지고온다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
1   (시험장의 갯수)
1   (각 시험장에 있는 응시자 수)
1 1 (감시할 수 있는 응시자 수 / 감시할 수 있는 응시자 수)

- 예제 출력 1 -
1

- 예제 입력 2 -
3
3 4 5
2 2

- 예제 출력 2 -
7

- 예제 입력 3 (반례) -
8
5 10 30 235 1 23 24 101
10 3

- 예제 출력 3
131

(3) 코드

# 틀린 코드
import math

n = int(input())
applicants = list(map(int, input().split()))
b, c = map(int,input().split())

answers = 0
for applicant in applicants:
    applicant = applicant - b

    # 나머지가 있는 경우
    if applicant%c > 0 :
        answer = applicant // c
        answer = math.floor(answer+1)

    # 나머지가 없는 경우
    elif applicant%c == 0:
        answer = applicant // c

    answers += answer+1

print(answers)

# 정답 코드

import math

n = int(input())
applicants = list(map(int, input().split()))
b, c = map(int,input().split())

answers = 0

for applicant in applicants:
    cnt = 0
    answer = 0
    if b >= applicant:
        cnt += 1

    elif b < applicant:
        applicant = applicant - b
        cnt += 1

        # 나머지가 있는 경우
        if applicant%c > 0 :
            portion = applicant // c
            portion = math.floor(portion+1)
            cnt += portion

        # 나머지가 없는 경우
        elif applicant%c == 0:
            portion = applicant // c
            cnt += portion

    answers += cnt

print(answers)

(4) 정리

주시험감독이 감시할 수 있는 수가 참가자보다 큰 경우인지 아닌지를 처음에 판단해줘야 합니다.
그렇지 않고 그냥 빼버리면 참가자가 마이너스가 되는 경우가 생겨서 한참 헤맸습니다.

(5) 참고

참고 반례

20364_부동산 다툼 (Python)

0. 출처

• 유형 : 트리 (silver 2)
• 링크 : 20364번: 부동산 다툼

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 땅의 갯수는 노드의 갯수이다. 6개이므로 7개 공간의 이차원 리스트를 만들자.
>> 이때 트리의 모양은 이진트리이다.
>> 이진트리처럼 만들어주려면 어떻게 해야할까? [[], [2,3],[4,5],[6]]
>> 오리의 번호 대로 방문표시를 해놓자.
>> 오리가 자기 번호로 가는길에 방문 표시를 한 땅을 밟은 경우 땅의 번호를 리턴하자.
>> 무사히 자기 땅에 간 경우는 0을 리턴하자.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
6 4 (땅의 갯수 / 오리의 수)
3 (오리가 가지고 싶어하는 땅의 번호)
5
6
2

- 예제 출력 1 -
0
0
3
0

(3) 코드

# 틀린 코드
# 디버깅용

from copy import deepcopy

n = int(6)
m = int(4)

num = n
temp = 0

tree = [[], [2, 3], [4, 5], [6]]
land_list = [3, 5, 6 ,2]

print(tree)

visited = deepcopy(tree)

def travel(start, land, flag, answer_list):
    if len(tree) > start:
        for index in range(len(tree[start])):
            if flag == False:
                return

            if tree[start][index] == land:
                visited[start][index] = 0
                flag = False
                answer_list.append(0)
                return flag

            elif tree[start][index] != land:
                if visited[start][index] == 0:
                    flag = False
                    answer_list.append(tree[start][index])
                    return flag
                elif visited[start][index] != 0:
                    next = tree[start][index]
                    flag = travel(next, land, flag, answer_list)
                    if flag == False:
                        return
    else:
        return

answer_list = []

print(land_list)

for land in land_list:
    flag = True

    travel(1, land, flag, answer_list)
    print(answer_list)

print(answer_list)

(4) 정리

로직을 아예 잘못짰다.
전체를 방문하다보니 방문한 곳의 자식노드가 내가 찾는 land 인지 아닌지를 구분해놓지 않아서
이미 방문한 곳이 visited = 0 인 경우 바로 해당 land를 반환하도록 짜버려서 답이 엉뚱하게 나왔다.
다시풀어보자.

(5) 참고

참고 풀이

9372_상근이의 여행 (Python)

0. 출처

• 유형 : 트리 (silver 3)
• 링크 : 9372_번: 상근이의 여행

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
2 (테스트 케이스 수)
3 3 (국가의 수 / 비행기의 종류)
1 2
2 3
1 3
5 4 (국가의 수 / 비행기의 종류)
2 1
2 3
4 3
4 5

- 예제 출력 1 -
2
4

(3) 코드

sample

(4) 정리

문제를 잘 못읽어 예제입력 예제출력이 왜 저렇게되나 한참봤다..
왜 예제출력 결과가 2개나 나오는지 때문에.. (맨 처음에 주어진게 테스트 케이스였음)
문제를 잘 읽자

또한 모든 국가가 연결되어있기 때문에 모든 국가를 방문하려면 국가의 갯수 - 1 이 정답이다.

(5) 참고

참고 풀이

9934_완전 이진 트리 (Python)

0. 출처

• 유형 : 트리 (silver 1)
• 링크 : 9934번: 완전 이진 트리

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 문제에서 주어진 방문순서는 중위 순회이다.
>> 레벨과 방문순서가 주어진다.
>> 주어진 것으로 트리의 정보를 구해야 한다.
>> 어떻게 구하지..?

>> 중위순회를 반대로 실행해야 한다.
>> level 활용하기
>> 중위순회 입력된 리스트 가운데가 항상 root 노드임을 활용하기
>> 중위 순회로 입력된 리스트를 왼쪽 부분 트리, 오른쪽 부분 트리로 쪼갤 줄 알아야한다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
2
2 1 3

- 예제 출력 1 -
1
2 3

- 예제 입력 2 -
3
1 6 4 3 5 2 7

- 예제 출력 2 -
3
6 2
1 4 5 7

(3) 코드

k = int(input())
inorder = list(map(int, input().split()))

answer = [[] for _ in range(k)]

def dfs(inorder, depth):

    # 트리의 root index를 찾아낸다.
    mid = (len(inorder) // 2)

    # 해당 깊이에 해당하는 node를 추가한다.
    answer[depth].append(inorder[mid])

    if len(inorder) == 1:
        return

    dfs(inorder[:mid], depth+1)
    dfs(inorder[mid+1:], depth+1)

dfs(inorder, 0)

for i in answer:
    print(*i)

(4) 정리

(5) 참고

참고 풀이

9934_[문제이름] (Python)

0. 출처

• 유형 : 트리 (silver 1)
• 링크 : 9934_번: 완전 이진 트리

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 문제에서 주어진 방문순서는 중위 순회이다.
>> 레벨과 방문순서가 주어진다.
>> 주어진 것으로 트리의 정보를 구해야 한다.
>> 어떻게 구하지..?

>> 중위순회를 반대로 실행해야 한다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
2
2 1 3

- 예제 출력 1 -
1
2 3

- 예제 입력 2 -
3
1 6 4 3 5 2 7

- 예제 출력 2 -
3
6 2
1 4 5 7

(3) 코드

sample

(4) 정리

(5) 참고

참고 풀이