본문 바로가기

Programming [Python]

 (411)
#224 백준 파이썬 [5585] 거스름돈 https://www.acmicpc.net/problem/5585 Python Code money = 1000 - int(input()) coin = 0 while money != 0: for num in [500, 100, 50, 10, 5, 1]: while money >= num: money -= num coin += 1 print(coin)
#223 백준 파이썬 [1697] 숨바꼭질 - BFS https://www.acmicpc.net/problem/1697 Solution 조금 다르게 (도착지 부터 계산) 시도해보려다가, 결국 같은 로직임을 깨달았다. B->A루트로 코드를 짰지만 A->B와 곱셈 나눗셈만 다르다. A에서 B까지 가장 빠르게 도달하는 방법은, A에서 갈 수 있는 모든 길을 1초 부터 찾는 것이다. 예를 들어 5 -> 17로 가는 길을 찾는다고 가정하면 0초에 갈 수 있는 수: 5 1초에 갈 수 있는 모든 수: 4, 6, 10 2초에 갈 수 있는 모든 수(이전 방문 수 제외): 3, 7, 8, 9, 11, 12, 20 3초에 갈 수 있는 모든 수(이전 방문 수 제외): ...16... 4초에 갈 수 있는 모든 수(이전 방문 수 제외): ...17... K에 도달하는 최소 값은 d..
#222 백준 파이썬 [7569] 토마토 - 3차원 BFS https://www.acmicpc.net/problem/7569 Solution https://claude-u.tistory.com/272와 같은 방법으로 풀 수 있다. 그러나 앞,뒤,좌,우,위,아래 총 6군데를 체크해주는 방식으로 간다. 아울러 모두 -1일 경우도 걸러준다. Python Code import copy from collections import deque M, N, H = map(int, input().split()) box = [[[]for _ in range(N)] for _ in range(H)] for h in range(H): for n in range(N): box[h][n]=list(map(int, input().split())) ripen_box = copy.deepcop..
#221 백준 파이썬 [7576] 토마토 - BFS https://www.acmicpc.net/problem/7576 Solution BFS로 구현할 수 있다. queue로 구햔하면 시간초과가 뜨기에 deque로 구현해준다. BFS로 해야, 1에서 최근접값을 찾을 수 있다. 1) 먼저 이미 익은 토마토를 queue에 넣고 2) queue안의 토마토를 앞에서부터 뽑아내준다. 3) 뽑아낸 토마토의 상하좌우에 안익은 토마토가 있으면 현재까지의 토마토 날에 +1을 해준다. 4) while문이 모두 돈 뒤, 0이 있으면 -1을 출력해주고, 없다면 배열 내의 최댓값 -1 을 출력해준다. Python Code import copy from collections import deque M, N = map(int, input().split()) box = [] for _..
#220 백준 파이썬 [11049] 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 Solution 파이썬으로는 느려서 풀지 못한다. pypy3로 풀 수 있는 문제 코드는 복잡해보이지만 은근히 간단하다. 우선 DP로 2차 행렬을 만들고 시작한다. ABCDE 까지 5개의 행렬이 있다고 생각해보자. 각각 (5, 7) (7,3) (3, 9) (9, 11) (11, 2) 라고 가정해보자. 새로운 dp라는 행렬을 만들어준다. 여기서 행과 열은 오른쪽 위만 쓴다. 각 칸의 의미는 i행렬부터 j행렬까지 행렬 곱의 최소값이다. A B C D E A B C D E 1. 먼저 각 행렬이 같은 부분에 0을 입력해준다. A B C D E A 0 B 0 C 0 D 0 E 0 2. A~B, B~C 등 1칸 차이가 나는 행렬들은 그냥 곱해주는것과..
#219 백준 파이썬 [1780] 종이의 개수 - 분할정복 https://www.acmicpc.net/problem/1780 Solution 쿼드 트리 문제들과 마찬가지로 풀되 (참고: https://claude-u.tistory.com/269) 4사분면이 아닌 9사분면으로 나누어 푼다. Python Code #나 트리 함수 정의 def nine_tree(x, y, n): global matrix, minus, zero, plus type = matrix[y][x] #첫 타입과 나머지 타입이 같아야함 double_break = False #for문 탈출용 double_break for i in range(x, x+n): if double_break: break for j in range(y, y+n): if matrix[j][i] != type: #하나라도 틀릴..
#218 백준 파이썬 [1992] 쿼드트리 - 분할정복 https://www.acmicpc.net/problem/1992 Solution 4사분면으로 나누는 쿼드트리, 분할 정복 문제이다. https://www.acmicpc.net/problem/2630문제와 완전히 같은 유형이라고 보면된다. Python Code #쿼드 트리 함수 정의 def quad_tree(x, y, n): global matrix, answer #배열 정보와 답이 될 변수를 끌어옴 color = matrix[y][x] #첫 색깔(흑백)과 나머지 색이 같아야함 double_break = False #for문 탈출용 double_break for i in range(x, x+n): if double_break: break for j in range(y, y+n): if matrix[j][..
#217 백준 파이썬 [2630] 색종이 만들기 - 분할 정복 https://www.acmicpc.net/problem/1992 #Solution 4사분면을 차례대로 정사각형으로 잘라 확인하는 분할정복 방법이다. 4개로 나뉜다고 하여 쿼드트리라 한다. #쿼드 트리 함수 정의 def quad_tree(x, y, n): global matrix, blue, white #주어진 배열과 색 카운트 끌어오기 color = matrix[y][x] #첫 색깔과 나머지 색이 같아야함 double_break = False #for문 탈출용 double_break for i in range(x, x+n): if double_break: break for j in range(y, y+n): if matrix[j][i] != color: #하나라도 틀릴시에 재귀문 생성 quad_tree..

티스토리툴바