11047_[문제이름] (Python)

0. 출처

• 유형 : 그리디 (silver 4)
• 링크 : 11047번: 동전 0

1. 기록

• 22/06/30 (목)

2. 풀이

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

1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>

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

- 예제 입력 1 -
동전의 갯수 / 가치의 합
10 4200
1
5
10
50
100
500
1000
5000
10000
50000


- 예제 출력 1 -
6

(3) 코드

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

n, k = map(int, input().split())
temp = deque([])
answer = 0

for _ in range(n):
    v = int(input())
    if v <= k:
        temp.appendleft(v)

for money in temp:

    a = k // money
    k -= (money * a)
    answer += a
    if n == 0:
        break

print(answer)

(4) 정리

처음부터 k의 값보다 큰 동전의 가치를 지닌것은 temp 에 추가하지 않았다.
또한 가치가 큰 동전부터 나열하는 식으로 추가해서 좀 더 for문을 쉽게 돌릴 수 있도록 하였다.

(5) 참고

9461_파도반 수열 (Python)

0. 출처

• 유형 : DP (silver 3)
• 링크 : 9461번: 파도반 수열

1. 기록

• 22/06/30 (목)

2. 풀이

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

1. 아이디어
>> DP
>> dp[i] = dp[i-2] + dp[i-3]

dp[1] = 1
dp[2] = 1
dp[3] = 1

2. 시간복잡도
>>

3. 자료구조
>>

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

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

t = int(input())

def dp_func(n):
    # fixme - 1. 테이블 정의
    dp = [0 for _ in range(101)]

    # fixme - 2. 초깃값 삽입
    dp[1] = 1
    dp[2] = 1
    dp[3] = 1

    # fixme - 3. 테이블 채우기
    for i in range(4, n+1):
        dp[i] = dp[i] = dp[i-2] + dp[i-3]

    print(dp[n])

for _ in range(t):
    n = int(input())
    dp_func(n)

(4) 정리

문제를 완전히 이해하지 않아도 숫자 규칙을 찾으면 DP 문제임을 알고 쉽게 풀 수 있는 문제였다.

(5) 참고

[문제번호]_[문제이름] (Python)

0. 출처

• 유형 : DP (silver 3)
• 링크 : 9095번: 1, 2, 3 더하기

1. 기록

• 22/06/30 (목)

2. 풀이

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

1. 아이디어
>> DP 문제 (tabulation 으로 푼다.)
>> 1. 테이블 정의
dp = [0 for _ in range(11)]

>> 2. 초깃값 삽입
dp[1]+3
dp[2]+2
dp[3]+1


>> 3. 테이블 채우기
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

2. 시간복잡도
>>

3. 자료구조
>>

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

- 예제 입력 1 -
3
4
7
10


- 예제 출력 1 -
7
44
274

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

t = int(input())

def dp_func(n):
    # fixme - 1. 테이블 정의
    dp = [0 for _ in range(11)]     # n은 11보다 작다는 조건이 있음, 테이블 크기를 11만큼 해주자

    # fixme - 2. 초깃값 삽입
    dp[0] = 0
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    dp[4] = 7

    # fixme - 3. 테이블 채우기
    for i in range(5, n+1):
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

    print(dp[n])

for _ in range(t):
    n = int(input())
    dp_func(n)

(4) 정리

DP 문제 풀면 짜릿하다.

(5) 참고

9375_패션왕 신해빈 (Python)

0. 출처

• 유형 : 해시 (silver 3)
• 링크 : 9375번: 패션왕 신해빈

1. 기록

• 22/06/30 (목)

2. 풀이

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

1. 아이디어
{
    'headgear':['hat','turban'],
    'eyewear':['sungalsses']
}

2. 시간복잡도
>>

3. 자료구조
>> 해시

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

- 예제 입력 1 -
테스트 케이스 / 해빈이가 가진 의상의 수
2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

- 예제 출력 1 -
5
3

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

t = int(input())

def OOTD(n):
    temp = {}

    for _ in range(n):
        wear, type = input().split()
        if type in temp:
            temp[type].append(wear)
        elif type not in temp:
            temp[type] = [wear]

    answer = 1

    for key in temp:
        answer *= (len(temp[key])+1)

    print(answer-1)

for _ in range(t):
    n = int(input())
    OOTD(n)

(4) 정리

(5) 참고

TEST

20056_마법사 상어와 파이어볼 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 4)
• 링크 : 20056번: 마법사 상어와 파이어볼

1. 기록

• 22/04/24 (일)

2. 풀이

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

1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>

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

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

from copy import deepcopy

n, m, k = map(int, input().split())
graph = [[[] for _ in range(n)] for _ in range(n)]

# graph에 상어가 있는 경우 [m, s, d] 로 저장하기
for _ in range(m):
    r, c, m, s, d = map(int, input().split())
    if m != 0:
        graph[r - 1][c - 1].append([m, s, d])

dirs = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]]

for _ in range(k):
    n_graph = [[[] for _ in range(n)] for _ in range(n)]

    # 1. 모든 파이어볼이 이동한다.
    for x in range(n):
        for y in range(n):
            if graph[x][y] != []:
                for b in range(len(graph[x][y])):
                    nm, ns, nd = graph[x][y][b]
                    nx = x + dirs[nd][0] * ns
                    ny = y + dirs[nd][1] * ns

                    nx = (nx + n) % n
                    ny = (ny + n) % n

                    n_graph[nx][ny].append([nm, ns, nd])

    # 2. 2개 이상의 파이어볼이 있는 칸을 찾아 4개의 파이어볼을 만든다.
    for x2 in range(n):
        for y2 in range(n):
            if len(n_graph[x2][y2]) > 1:
                cm, cs, cd = 0, 0, []
                cnt = len(n_graph[x2][y2])

                for c in range(cnt):
                    cm += n_graph[x2][y2][c][0]
                    cs += n_graph[x2][y2][c][1]
                    cd.append(n_graph[x2][y2][c][2] % 2)
                cm = int(cm / 5)
                cs = int(cs / cnt)
                n_graph[x2][y2] = []

                if cm != 0:  # 질량이 0 인 경우 소멸하는 조건 고려
                    if sum(cd) == 0 or sum(cd) == cnt:  # 합쳐지는 파이어볼 방향이 모두 홀수거나 짝수인 경우
                        for i in range(4):
                            n_graph[x2][y2].append([cm, cs, i * 2])
                    else:
                        for j in range(4):
                            n_graph[x2][y2].append([cm, cs, j * 2 + 1])

    graph = deepcopy(n_graph)

# 남아있는 파이어볼 질량의 합 구하기
sum_m = 0
for x in range(n):
    for y in range(n):
        if graph[x][y] != []:
            for b in range(len(graph[x][y])):
                sum_m += graph[x][y][b][0]
print(sum_m)

(4) 정리

내가 놓친 부분
주어진 파이어볼의 정보를 graph 상에 잘 옮겨 놨으나
파이어 볼 이동을 한개씩을 graph 상에 옮기고 파이어볼을 나누고 옮기고 나누고해서 계속 실패했습니다.
파이어 볼이 이동한 위치, m,s,d 등을 다른 3차원 배열상에 전체를 옮겨놓은 뒤에
파이어 볼을 전체를 4방향으로 나누는 과정을 진행해야 합니다.
따라서 이러한 문제에서 deepcopy 등이 자주 사용됨을 기억하면 좋을 것 같습니다.★

(5) 참고

가장 이해가 잘된 풀이

20057_마법사 상어와 토네이도 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 3)
• 링크 : 20057번: 마법사 상어와 토네이도

1. 기록

• 22/04/23 (토)

2. 풀이

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

1. 아이디어
>> 토네이도가 격자의 가운데 부터 시전한다. n 이 홀수여야 함
>> 토네이도의 회전 모양을 코드로 어떻게 표현할 것인가? 규칙성을 찾자
>> n = 5 인 경우
>> 1칸 2번, 2칸 2번, 3칸 2번, 4칸 2번, 5칸 1번 (마지막의 경우 범위를 벗어나면 종료되도록 한다.)

>> 퍼지는 값
>> dx = [-1, 1, -2, 2, 0, -1, 1, -1, 1]
>> dy = [1, 1, 0, 0, -2, 0, 0, -1, -1]

2. 시간복잡도
>>

3. 자료구조
>>

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

- 예제 입력 1 -
5
0 0 0 0 0
0 0 0 0 0
0 10 0 0 0
0 0 0 0 0
0 0 0 0 0

- 예제 출력 1 -
10

- 예제 입력 2 -
5
0 0 0 0 0
0 0 0 0 0
0 100 0 0 0
0 0 0 0 0
0 0 0 0 0

- 예제 출력 2 -
85

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

- 예제 출력 3 -
139

(3) 코드

# 모래 계산하는 함수
def recount(block, dx, dy, direction):
    global ans, s_x, s_y

    # y좌표 계산 & x좌표 갱신
    for _ in range(block):
        s_x += dx
        s_y += dy
        if s_y < 0:  # 범위 밖이면 stop
            break

        # 3. a, out_sand
        total = 0  # a 구하기 위한 변수

        for dx, dy, z in direction:
            nx = s_x + dx
            ny = s_y + dy

            # 원래모래에서 - 퍼진모래 = 이동한 방향에 남은 모래
            if z == 0:
                new_sand = sand[s_x][s_y] - total

            # 퍼지는 모래양에 모래비율을 곱해준다. 
            elif z != 0:
                new_sand = int(sand[s_x][s_y] * z)
                total += new_sand

            if 0 <= nx < N and 0 <= ny < N:   # 인덱스 범위이면 값 갱신
                sand[nx][ny] += new_sand
            elif not(0 <= nx < N and 0 <= ny < N):  # 범위 밖이면 ans 카운트
                ans += new_sand


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

# 2. 방향별 모래 비율 위치
left = [(1, 1, 0.01), (-1, 1, 0.01), (1, 0, 0.07), (-1, 0, 0.07), (1, -1, 0.1),
         (-1, -1, 0.1), (2, 0, 0.02), (-2, 0, 0.02), (0, -2, 0.05), (0, -1, 0)]
right = [(x, -y, z) for x, y, z in left]
down = [(-y, x, z) for x, y, z in left]
up = [(y, x, z) for x, y, z in left]

s_x, s_y = N//2, N//2  # 시작좌표(x좌표)
ans = 0  # out_sand

# 1. 이동하는 칸 수
for block in range(1, N + 1):
    # 움직이는 칸 수가 홀수인 경우
    if block % 2 == 1:
        recount(block, 0, -1, left)
        recount(block, 1, 0, down)

    # 움직이는 칸 수가 짝수인 경우
    elif block % 2 == 0:
        recount(block, 0, 1, right)
        recount(block, -1, 0, up)

print(ans)

(4) 정리

토네이도의 회전방향을 계속 고려해줘야 한다는 점

토네이도 이동방향에 따른 모래가 퍼지는 방향이 다르다는 점

위 두가지가 생각보다 까다로워서 풀이를 찾아봤습니다.

또한 토네이도 이동방향에 따라 모래가 퍼지는 방향을 하드코딩하는 방법 말고는 시간 내에 떠올리지 못했을거 같습니다.

(5) 참고

참고 풀이

19236_청소년 상어 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 2)
• 링크 : 19236번: 청소년 상어

1. 기록

• 22/04/21 (목)

2. 풀이

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

1. 아이디어
>> [[[물고기번호, 방향], [물고기번호, 방향], [물고기번호, 방향]],
    [[물고기번호, 방향], [물고기번호, 방향], [물고기번호, 방향]],]

>> 이렇게 3차원 배열형태로 담는다.

----------------------------------------------------------------------------------------------
>> 상어는 [0] 을 먹으면 [0][0] 의 물고기번호를 누적하고 [0][1] 의 방향을 갖게된다.
>> 이후 물고기번호 1번부터 끝번호까지 해당 방향으로 이동할 수 있으면 이동하고
>> 이동할 수 없으면 45도 반시계방향으로 회전한다. (해당 방향에 상어가 있는 경우도 이동할 수 없는 경우이다.)

>> 상어는 [0][1] 방향을 가졌으므로 
>> 해당 방향으로 1번 이동하는 경우, 2번 이동하는 경우, ...를 모든 경우르 비교한다.
>> 상어는 여러칸을 이동할 수 있기 때문에 백트래킹으로 풀어야한다. ★★★★★
----------------------------------------------------------------------------------------------

>> 위의 경우를 계속 반복하고 상어가 더 이상 이동할 수 없는 경우 누적된 물고기 번호 합을 리턴한다. 

2. 시간복잡도
>>

3. 자료구조
>>

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

- 예제 입력 1 -
7 6 2 3 15 6 9 8
3 1 1 8 14 7 10 1
6 1 13 6 4 3 11 4
16 1 8 7 5 2 12 2

- 예제 출력 1 -
33

- 예제 입력 2 -
16 7 1 4 4 3 12 8
14 7 7 6 3 4 10 2
5 2 15 2 8 3 6 4
11 8 2 4 13 5 9 4

- 예제 출력 2 -
43

- 예제 입력 3 -
12 6 14 5 4 5 6 7
15 1 11 7 3 7 7 5
10 3 8 3 16 6 1 1
5 8 2 7 13 6 9 2

- 예제 출력 3 -
76

- 예제 입력 4 -
2 6 10 8 6 7 9 4
1 7 16 6 4 2 5 8
3 7 8 6 7 6 14 8
12 7 15 4 11 3 13 3

- 예제 출력 4 -
39

(3) 코드

import copy

n = int(4)
m = int(8)

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

graph = list([] * n for _ in range(n))

for i in range(n):
    for j in range(0, m, 2):
        graph[i].append(temp_graph[i][j:j + 2])

for i in range(n):
    for j in range(n):
        graph[i][j][1] -= 1

# 방향
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

# 상어가 [0][0]의 위치로 간다.
# [행][열][0] : 먹이번호
# [행][열][1] : 방향

max_score = 0
def dfs(sx, sy, total, graph):

    global max_score

    total += graph[sx][sy][0]
    max_score = max(max_score, total)

    graph[sx][sy][0] = 0

    # 물고기 움직임
    for num in range(1, 17):
        f_x, f_y = -1, -1
        for x in range(n):
            for y in range(n):
                if graph[x][y][0] == num:

                    f_x, f_y = x, y
                    break

        if f_x == -1 and f_y == -1:
            continue

        f_d = graph[f_x][f_y][1]

        for i in range(8):
            nd = (f_d + i) % 8
            nx = f_x + dx[nd]
            ny = f_y + dy[nd]

            # 범위를 벗어나는 경우 or 상어가 있는 경우는 건너 뛴다.
            if not (0 <= nx < 4 and 0 <= ny < 4) or (nx == sx and ny == sy):
                continue

            # 조건을 만족하는 경우 해당 물고기의 방향
            graph[f_x][f_y][1] = nd

            # 해당 물고기와 해당 물고기가 가리키는 방향에 위치한 물고기의 위치를 바꿔준다.
            graph[f_x][f_y], graph[nx][ny] = graph[nx][ny], graph[f_x][f_y]
            break

    s_dir = graph[sx][sy][1]
    for i in range(1, 4):
        nx = sx + dx[s_dir] * i
        ny = sy + dy[s_dir] * i

        if (0 <= nx < 4 and 0 <= ny < 4) and graph[nx][ny][0] > 0:
            dfs(nx, ny, total, copy.deepcopy(graph))

dfs(0, 0, 0, graph)
print(max_score)

(4) 정리

(5) 참고

참고 풀이

20058_마법사 상어와 파이어스톰 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 4)
• 링크 : 20058번: 마법사 상어와 파이어스톰

1. 기록

• 22/04/22 (금)

2. 풀이

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

1. 아이디어
>> n을 입력받는다. -> 2^n = 행의 갯수, 열의 갯수
>> 인접해있는 얼음칸의 갯수가 3개 이상인지 어떻게 판단하는게 좋을지?
>> 모두 돌아서 3개미만인 칸의 좌표를 append해주자.
>> 이후 해당 좌표의 얼음을 -1 해준다. 얼음이 바깥쪽부터 안쪽으로 파고드는형태로 녹을 것임.

# 파이어 스톰 시전
>> 파이어 스톰에 해당하는 격자의 크기 만큼 쪼갠다. -> how?
>> for i in range(0, m, 2^k) (시전한 숫자의 지수승 값만큼 이동)
>>  for j in range(0, m, 2^k)

>> 해당 격자를 90도 만큼 시계방향으로 돌린다. [i,j] -> [j, (n-1)-i]
>> 시계 방향으로 돌린 격자를 다른 map 등에 저장하고 다시 graph에 할당하는 식으로 한다.


2. 시간복잡도
>>

3. 자료구조
>>

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

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

from pprint import pprint
from collections import deque

# n, q 를 입력 받는다.
n, q = map(int, input().split())
m = 2**n

# graph 를 입력받는다.
graph = list(list(map(int,input().split())) for _ in range(m))

# 마법 사이즈를 입력받는다.
magics = deque(list(map(int, input().split())))
m = 2**n

# 주변 얼음갯수를 카운트해주는 함수
def ice3(x,y, ice_cnt):
    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 범위에 벗어나지 않으면서 인접 위치에 얼음이 있으면
        if 0 <= nx < m and 0 <= ny < m and graph[nx][ny] >= 1 and graph[x][y] >= 1:
            ice_cnt[x][y] += 1

    return ice_cnt

# 마법 끝날때 까지
while magics:

    # k는 지수승할 숫자
    k = magics.popleft()
    s = 2 ** k

    # map = [[0] * m for _ in range(m)]
    # 격자를 나누고 시계방향으로 90도 회전시킨다.
    for x in range(0, m, s):
        for y in range(0, m, s):
            tmp = [graph[i][y:y+s] for i in range(x, x+s)]
            print(f"tmp입니다. {tmp}")
            for i in range(s):
                for j in range(s):
                    graph[x + j][y + s - 1 - i] = tmp[i][j]

    # 주변 얼음 갯수를 카운트 해준다.
    ice_cnt = [[0] * m for _ in range(m)]
    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]
    for x1 in range(m):
        for y1 in range(m):
            ice3(x1,y1, ice_cnt)

    # 조건에 만족하지않는 얼음의 갯수를 -1 해준다.
    for x2 in range(m):
        for y2 in range(m):
            if ice_cnt[x2][y2] >= 0 and ice_cnt[x2][y2] < 3:
                if graph[x2][y2] >= 1:
                    graph[x2][y2] -= 1


# graph에 있는 얼음의 갯수와 최대 얼음덩어리의 칸의 갯수를 세어준다.
total_ice = 0

for i in range(m):
    for j in range(m):
        total_ice += graph[i][j]

def last(x, y, visited, max_mass, mass):
    q = deque()
    q.append((x,y))
    visited[x][y] = True
    while q:
        x, y = q.popleft()
        dx = [0, -1, 0, 1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<m and 0<=ny<m and visited[nx][ny] == False and graph[nx][ny] >= 1:
                visited[nx][ny] = True
                q.append((nx, ny))
                mass += 1
    return mass

visited = [[False]*m for _ in range(m)]
max_mass = 0

for i in range(m):
    for j in range(m):
        if graph[i][j] > 0 :
            mass = 1
            mass = last(i, j, visited, max_mass, mass)
            if max_mass < mass:
                max_mass = mass

print(total_ice)
print(max_mass)

(4) 정리

이 문제에서 가장 어려운 부분은
원하는 격자만큼 어떻게 쪼갤 것인가 ★
쪼갠 격자를 어떻게 90도 만큼 시계방향으로 회전시킬 것인가 이다. ★
무려 4중 for문을 이용해야한다.
시험에서 이 방법을 어떻게 생각할지 의문이다.
문제 읽고 문제풀이 코드 이해하는데까지 4시간 걸렸다.
다음 사진으로 핵심 부분을 이해하시면 좋을 듯하다.

90도 시계방향으로 회전하는 로직 이해하기

격자로 쪼개고 90도 시계방향으로 회전하는 로직

(5) 참고

참고 풀이