[이취코] 음료수 얼려먹기 / BFS / Python
2024. 11. 21. 22:50
2차원 배열에서 0은 빈공간, 1은 벽얼음 개수를 구하는거라 0으로 구성된 묶음이 총 몇 개인지 구하면 됨 BFS의 전통적인 문제로... 전설의 문제 '그림'과 같은 형태 from collections import dequen,m = map(int,input().split())a = [list(map(int,input().strip())) for _ in range(n)]visited = [[False for _ in range(m)] for _ in range(n)]dx=[0,0,1,-1]dy=[1,-1,0,0]def bfs(i,j): q = deque() q.append([i,j]) visited[i][j]=True while q: cur = q.popleft() ..
[이취코] DP 실전 - 못생긴 수 / Python
2024. 11. 21. 22:05
2,3,5만을 약수로 가지는 합성수를 못생긴 수라고 한다1은 못생긴 수라고 가정한다n번째 못생긴 수를 구하자 처음 아이디어 접근 일단 1,2,3,4,5가 못생긴 수인건 맞으니dp = [1,1,1,1,1] 로 세팅한다 n이 5보다 작은 경우에는 n을 return하도록 한다 그 이상은 dp를 구한다 못생긴 수를 세는 cnt와 현재 수를 나타내는 cur 변수를 둔다while문을 돌며 cnt가 n에 도달하면 멈춘다 while문 내에서 현재 살펴보는 수를 1씩 증가시킨다현재 수가 2or3or5로 나누어떨어지고, dp[i//(2or3or5)-1]값이 1이라면그 수는 2,3,5만을 인수로 가진다는 뜻못생긴 수 cnt를 증가시키고, dp에도 못생긴 수라는 뜻으로 1을 삽입 그 외에는 0을 삽입한다 마지막에 현재 숫자를..
