[백준] CLASS 3 달성하기 7일차

이진규·2022년 7월 17일
1

백준(PYTHON)

목록 보기
53/115

1. DSLR(★BFS)

링크 : https://www.acmicpc.net/problem/9019

from collections import deque
from sys import stdin
input = stdin.readline

T = int(input())

for _ in range(T):
    a, b = map(int, input().split())

    def bfs(v, move):
        visited = [0] * (10000+1)
        visited[v] = move
        q = deque([(v, move)])

        while q:
            v, move = q.popleft()

            if v == b:
                print(visited[v])
                return

            for x in ('D', 'S', 'L', 'R'):
                if x == 'D':
                    value = 2 * v
                    if value > 9999:
                        value %= 10000

                    if visited[value] == 0:
                        visited[value] = move + 'D'
                        q.append((value, move+'D'))
                elif x == 'S':
                    value = v - 1
                    if v == 0: # 문제 잘 읽어야 하는 부분, v-1 == 0이 아니라 v == 0 인 경우임.
                        value = 9999

                    if visited[value] == 0:
                        visited[value] = move + 'S'
                        q.append((value, move+'S'))
                        
                # 123에서 'L' 연산시에는 1230이, 'R' 연산시에는 3012가 출력되어야 한다.
                elif x == 'L': # 문자열로 바꿔서 연산 후 숫자로 바꾸는 과정은 시간초과가 걸리기 때문에 다음과 같은 로직이 필요하다.
                    front = v % 1000
                    back = v // 1000
                    value = front * 10 + back

                    if visited[value] == 0:
                        visited[value] = move + 'L'
                        q.append((value, move+'L'))
                elif x == 'R': # 문자열로 바꿔서 연산 후 숫자로 바꾸는 과정은 시간초과가 걸리기 때문에 다음과 같은 로직이 필요하다.
                    front = v % 10
                    back = v // 10
                    value = front * 1000 + back

                    if visited[value] == 0:
                        visited[value] = move + 'R'
                        q.append((value, move+'R'))

    bfs(a, '')

참고자료

링크 : https://paris-in-the-rain.tistory.com/94

  • 왼쪽 시프트 연산, 오른쪽 시프트 연산 볼 필요 있음

2. 1, 2, 3 더하기(DP)

링크 : https://www.acmicpc.net/problem/9095

from sys import stdin
input = stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())
    dp = [0, 1, 2, 4]

    for i in range(4, n+1):
        dp.append(dp[i-1] + dp[i-2] + dp[i-3])

    print(dp[n])

3. 패션왕 신해빈(해싱)

링크 : https://www.acmicpc.net/problem/9375

from sys import stdin
input = stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())
    clothes = {}

    for _ in range(n):
        cloth, item = input().split()

        if item in clothes: # 옷의 품목과 가짓수 기록
            clothes[item] += 1
        else:
            clothes[item] = 1

    answer = 1
    for key, value in clothes.items():
        answer *= (value + 1) # 해당 옷을 입는 경우와 안입는 경우를 곱집합으로 계산

    print(answer - 1) # -1을 해주는 이유는 옷을 전부 안입는 경우(알몸 상태)를 제거해주기 위함.

4. 파도반 수열(DP)

링크 : https://www.acmicpc.net/problem/9461

from sys import stdin
input = stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())
    dp = [0, 1, 1, 1]

    for i in range(4, n+1):
        dp.append(dp[i-2] + dp[i-3])

    print(dp[n])

5. 적록색약(BFS)

링크 : https://www.acmicpc.net/problem/10026

  • 일반 사람이 볼때는 그냥 bfs를 돌리고 적록색약인 사람이 볼때는 bfs를 돌리기 전에 R,G의 색깔을 하나로 통일시키고 bfs를 돌린다.
import sys
input = sys.stdin.readline

from collections import deque

n = int(input())
photo = [list(input().strip()) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
ans = []

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

def bfs(x, y):
    visited[x][y] = True
    q = deque([(x, y)])

    while q:
        px, py = q.popleft()
        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]
            if 0 <= mx < n and 0 <= my < n:
                if photo[mx][my] == photo[px][py] and not visited[mx][my]:
                    visited[mx][my] = True
                    q.append((mx, my))

for _ in range(2):
    cnt = 0

    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                bfs(i, j)
                cnt += 1

    ans.append(cnt)

    for i in range(n):
        for j in range(n):
            visited[i][j] = False
            if photo[i][j] == 'R':
                photo[i][j] = 'G'

print(*ans)

6. 동전0(그리디)

링크 : https://www.acmicpc.net/problem/11047

  • 그리디 : 가장 욕심내서 이득을 취해야 함.
from sys import stdin
input = stdin.readline

n, k = map(int, input().split())
coin = []

for _ in range(n):
    coin.append(int(input()))

coin.sort(reverse=True)

answer = 0
for i in range(n):

    if k >= coin[i]:
        answer += (k // coin[i])
        k %= coin[i]

print(answer)

7. 최대 힙(최대 힙)

링크 : https://www.acmicpc.net/problem/11279

import heapq
from sys import stdin
input = stdin.readline

n = int(input())
heap = []

for _ in range(n):
    x = int(input())

    if x == 0:
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(0)

    else:
        heapq.heappush(heap, -x)
profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글