본문 바로가기

Algorithm175

2624. 동전 바꿔주기 (Python) 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 풀이 1차원 dp를 사용하는데 dp 배열의 의미는 다음과 같다. dp[n] : 금액 n의 동전 교환 방법 경우의 수 모든 dp 배열의 값은 0으로 초기화 되지만 dp[0]은 아무 동전도 사용하지 않는 경우 하나가 존재한다고 가정하여 dp[0]은 1로 초기화한다. 경우의 수를 구하기 위한 점화식은 다음과 같다. dp[money] += dp[money - coin * cnt] (money는 구하기 위한 금액, coin은 현재 사용하는 동전의 금액,.. 2022. 6. 11.
1774. 우주신과의 교감 (Python) 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 최소 신장 트리(MST)를 이용하여 해결하는 문제이다. MST를 만드는 방법에는 크루스칼 알고리즘과 프림 알고리즘이 있다. 자세한건 검색을 통해 알아보자. 간단하게 설명하면 다음과 같다. * 크루스칼 알고리즘 : 모든 간선을 길이에 따라 오름차순으로 정렬하여 크기가 작은 간선부터 사용한다. 간선을 사용했을 때 사이클이 발생하지 않는지를 체크한다. * 프림 알고리즘 : 시작 정점을 기준으로 선택할 수 있는 간선 중 가장 크기가 작은.. 2022. 6. 10.
17071. 숨바꼭질 5 (Python) 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 시간 제한이 0.25초로 빡빡하기 때문에 일반적인 방문체크로는 정답을 구할 수 없다. 이때 필요한 것이 짝수초와 홀수초로 나누어 방문 체크를 하는 것이다. 예를 들어 수빈이가 10의 위치에 2초에 도착했다고 가정해보자. 수빈이는 X-1이나 X+1을 이동할 수 있다. 즉, 10에서 왼쪽으로 한 번 이동하고 오른쪽으로 한 번 이동하는 방식으로 다시 같은 위치로 이동할 수 있다. 10의 위치에 2 + 2초, 2 + 4초, 2 .. 2022. 6. 9.
17136. 색종이 붙이기 (Python) https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 1이 적힌 칸에서 1x1 크기의 색종이부터 5x5 크기의 색종이까지 붙일 수 있는지를 체크한다. 색종이를 붙이고 나면 색종이로 덮어진 부분을 체크해주고 다음 1이 적힌 칸으로 넘어가서 색종이를 붙일 수 있는지를 체크하는 과정을 반복한다. 모든 1이 적힌 칸을 색종이로 덮고 나면 사용한 색종이의 개수들을 비교하여 그 중 최소 개수를 기록하면 된다. 코드 # size * size 색종이.. 2022. 6. 7.
2240. 자두나무 (Python) 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 풀이 3차원 dp 배열을 이용하여 문제를 해결할 수 있다. 3차원 dp 정보는 다음과 같다. dp[t][w][p] : t시간에 w번 이동하여 p번 나무에 있을 때 받을 수 있는 자두의 최대 개수 처음에는 1번 자두 나무에 위치하므로 이에 대하여 따로 처리해준다. 만약 처음으로 떨어지는 자두의 위치가 1일 경우에는 이동하지 않고 자두를 받을 수 있으므로 dp[1][0][1]을 1로 설정한다. 처음으로 떨어지는 자두의 위치가 2일 경우에는 한 번 이동해야 받을 수 있으므로 .. 2022. 6. 6.
2141. 우체국 (Python) 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 풀이 그리디에 해당하는 문제인데 모르겠어서 다른 사람의 풀이를 참고했다. 우체국의 위치를 구하려면 우체국을 세운 지점 기준으로 왼쪽에 위치한 사람의 숫자와 오른쪽에 위치한 사람의 숫자의 차가 최소가 되는 지점을 찾아야 한다. 먼저 입력으로 받은 마을 위치를 기준으로 오름차순 정렬한 후 처음부터 끝까지 우체국을 세워가며 왼쪽과 오른쪽 사람의 수를 누적합을 사용하여 체크한다. 두 누적.. 2022. 6. 4.

티스토리툴바