맛대의 블로그

https://www.acmicpc.net/problem/3067로직가정 : 동전은 1,3원이 있음1원만으로 1원, 2원, 3원 ... 15원을 만드는 방법은 모두 1가지여기에 3원을 추가하면 1,2원을 만드는 방법은 1개 그대로지만, 3원을 만드는 방법은 2개가 됨 (1+1+1, 3)4원, 5원도 마찬가지로 방법이 2개(1+1+1+1, 1+3) ...6원을 만드는 방법은 기존에 1원만으로 6원을 만드는 방법 + 3원을 만드는 방법에서 3원짜리 동전을 추가하는 방법x원을 만드는 방법이 f(x)라고 했을 때, f(6) = f(6) + f(6-3)의 방정식이 성립````pythondef solution(coins:list[int],M:int)->int: record = [0]*(M..

https://www.acmicpc.net/problem/4991 로직 bfs 활용 먼저 로봇청소기가 있는 지점에서 bfs를 통해 각 먼지까지의 거리를 구함 방문할 수 없는 더러운 곳이 있다면, 이 때 거리를 통해 알 수 있음 그 후 먼지 위치에서 bfs를 통해 각 먼지까지의 거리를 구함 이렇게 구한 로봇청소기,먼지 사이의 거리를 2중 배열 graph[r][c]형식으로 graph로 만들어 기록 로봇청소기 위치를 시작지점으로 브루트포스 방식으로 먼지들을 방문하며 합계 거리를 계산 (함수명 recur) 이 때 이미 최단 거리 보다 합계 거리가 멀어질 경우 백트레킹 from collections import deque import sys input = sys.stdin.readline def makeGraph..

https://www.acmicpc.net/problem/18224 로직 bfs 문제 밤에만 벽을 넘을 수 있으므로 현재 몇번 이동했는지에 따라 상태가 다르게 됨 arr = [ [0,0,1,1] [1,1,1,1] [1,1,1,1] [0,1,1,0] ] 미로가 위와 같다고 할때 밤이 되기 전까지 0,0과 0,1을 왕복하게 됨 이 때 몇번째 이동 했는지에 따라 상태가 다른데, 이는 밤이 되기까지 얼마나 남았는지가 다르기 때문 따라서 방문을 체크할 변수를 nn이 아닌 n*n(2*m)배열로 만듬 2m인 것은 하루동안 2m 걸음만큼 이동이 가능하므로 각각이 상태가 다르기 떄문 만약 1일차 첫번쨰 걸음에 0,0이였는데, 2일차 첫번쨰 걸음이 0,0이라면 똑같은 상태이기 떄문에 방문처리로 인해 연산을 멈춤 from ..

https://www.acmicpc.net/problem/28131 로직 다익스트라 알고리즘 활용 기본적인 다익스트라 알고리즘은 최소값을 저장 이 문제의 경우 정확하게 K로 나눠떨어져야해서 최소값만 저장해서는 안되는 경우가 많음 그렇기에 K로 나눈 나머지 값을 idx로 활용하여, 각각의 idx마다 최소값을 기록 1에서 2지점 가는데 3,4 원으로 가는 방법이 있고, K가 2일때 [3,4] 형태로 값을 기록 기본적으로 주어지는 a지점에서 b지점 가는길이 한개가 아닐 수 있음 그리고 그 값중에 최소값 이외의 값도 필요 c원과 c+d*K원이 있을 경우를 제외하고 싶었지만, N의 값 혹은 a->b 지점으로 가는 길이 너무 많을 경우 그 자체만으로도 시간복잡도가 큼 from heapq import heappop,..

https://www.acmicpc.net/problem/2169 로직 로봇은 아래,오른쪽,왼쪽으로만 움직이며 한번 지나친 곳은 지나가지 못함 그렇기에 해당 row에서 한번 왼쪽으로 움직으면 왼쪽으로만, 오른쪽으로 움직이면 오른쪽으로만 움직일 수 있음 왼쪽으로 움직였을 경우와 오른쪽으로 움직였을 경우 두가지로 나누어 계산하면 모든 경우의 수 계산이 가능해짐 r,c 지점에서의 최대 값은 윗층(r-1,c)에서 내려온 값, 왼쪽(r,c-1)에서 온 값, 오른쪽(r,c+1)에서 온 값 세가지로 분류 가능 이를 왼쪽, 오른쪽으로만 움직일 경우로 분리하고 각각의 경우에 최대값을 찾은 후 병합하는 방식 import sys input = sys.stdin.readline def solution(R,C,arr): for..

https://www.acmicpc.net/problem/2565 로직 dp(dynamic programing)문제 전기줄이 안꼬이는 방법 시작지점을 기준으로 정렬 도착지점이 기존의 최대 값보다 높으면 꼬이지 않음 기존의 최대 값보다 낮으면 꼬이게 되므로 기존의 높이와 비교하며 계산 만약 기존의 최대 값보다 낮은 경우엔 기존 최대값인 선을 잘라버리고 해당 선을 이용하면 다음 선이 좀 더 안꼬이게 됨 변수 record :list[int] 구조로 index와 그 값이 의미 하는 것은 전기줄을 index개수 만큼 안꼬인 경우 높이(값) 그렇기에 이번 전선이 record[index] 값 보다 높으면 전기줄이 안꼬이며 쌓아갈 수 있다는 것을 의미 record[index] 값 보다 낮으면 기존 전선을 잘라버리고 해..

https://www.acmicpc.net/problem/13424 로직 친구들이 있는 지점에서 각 방까지의 거리를 구하는 문제 다익스트라, 플로이드 워셜 알고리즘을 이용하면 쉽게 해결 가능 문제상 i번 노드에서 i번 노드로 가는 길을 0으로 처리 해둬야함 다익스트라 다익스트라의 경우 graph[a]조회시 (b,c)형태로 도착지, 길이를 조회하는 방식으로 N번까지 전체 조회를 하지 않는 방식 채택하여 연산을 줄임 모든 지점에 친구가 있으면 의미가 없지만, 친구가 있는 지점을 기준으로 최단 거리를 구하여 평균적인 연산을 줄임 import sys input = sys.stdin.readline from heapq import heappush,heappop def dijkstra(N,startNode,grap..

https://www.acmicpc.net/problem/9421 로직 2부터 n까지의 소수를 구한다 primeNumList 함수(에라토스테네스의 체 활용) 소수가 상근수인지 확인 재귀 방식을 이용하여 확인 재귀 도중 같은 수가 여려번 나올 수 있으니 기존에 계산했던 경우 그 값을 활용(변수명 checkList) 무한 루프에 빠질 수 있으므로 재귀 전에 현재의 수를 상근수가 아니다로 표기 후 재귀 def primeNumList(n): check = [False,False]+[True]*(n-1) for num in range(2,(n+1)//2): if check[num]: for multiNum in range(2*num,n+1,num): check[multiNum] = False value = lis..

https://www.acmicpc.net/problem/9370 로직 다익스트라 알고리즘을 이용하여 최단거리를 구함 g -> h 혹은 h -> g로 이동할 때를 찾아야 함 시작점 -> g -> h -> 목적지 시작점 -> h -> g -> 목적지 시작점에서 목적지까지의 최단거리가 위의 방법과 거리가 같다면 g-h 도로를 이용하여 이동 할 수 있음을 알 수 있음 만약 같은 길이의 다른 경로가 존재 하더라도, g-h 도로를 이용하여 갈수도 있으므로 가능성이 있는 목적지 만약 더 짧은 길이의 다른 경로가 존재한다면, 시작점-목적지 까지의 최단거리가 위의 방법과 같을 수가 없음 그렇기에 시작점에서 g,h,목적지 까지의 최단거리 // g->h, g->목적지 까지의 최단 거리 // h->g,h->목적지 까지의 최..

https://www.acmicpc.net/problem/11780 로직 최단 거리는 플로이드 워셜 알고리즘 활용 모든 노드에 관하여 3중 반복문 활용(중간점, 시작점, 끝나는 점) 기존의 시작점-끝난점 거리보다 중간점에 들리는 경우가 더 짧은 경우 갱신하는 알고리즘 경로를 파악하기 위해 플로이드 워셜 알고리즘으로 갱신되는 경우 중간 지점을 기록 기록해둔 중간지점을 이용하여 병합하는 형식으로 루트를 파악 1번에서 10번 지점까지의 경로를 찾는다고 가정 1번에서 10번 가려는데 최단거리를 위해 중간에 거치는 경로가 5번이라고 하면 1 .... 5 ...... 10번 경로를 통해 최단 거리가 될 수 있음을 알 수 있음 이제 1에서 5번까지의 경로를 확인하고, 5번에서 10번까지의 경로를 확인 마찬가지로 1에..