본문 바로가기
728x90

전체 글432

[python] 백준 1943 동전 분배 https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원 www.acmicpc.net 문제 해결 먼저 돈의 총 합을 보았을 때 홀수이면 나눌 수 없다는 것을 알 수 있다. 짝수여도 무조건 가능한 것은 아니지만 총합의 절반을 나눌 수 있다. 절반을 가지고 가지고 있는 동전을 조합하여 맞출 수 있는가?를 보면 된다. 이는 DP를 가지고 풀 수 있다. 처음에는 이론상 0원만 가능하고 동전의 종류별로 채워나가며 dp[total]이 True가 된다면 만들 수 있는 것이다. 만.. 2024. 2. 7.
[python] 백준 1513 경로 찾기 https://www.acmicpc.net/problem/1513 1513번: 경로 찾기 첫째 줄에 0개 방문했을 때, 1개 방문했을 때, ..., C개 방문했을 때 총 경로의 개수를 한 줄에 공백을 사이에 두고 출력한다. 경로의 개수는 1,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 문제 해결 집에서 학원을 가면서 PC방을 몇 개를 자나가는지 문제 지나가는 개수는 상관이 없으나 순서가 존재 이를 DP를 이용할지 DFS를 이용할지 생각을 해봐야한다. 숫자가 작아서 DFS를 사용해도 될 것 같지만 하나씩 끝까지 갔다가 다시 돌아오는 것보다 DP를 이용해 4차원(현재 행, 현재 열, 오락실 중 최대 번호, 방문한 오락실 개수)로 계산하여 한번에 경우의 수를 계산하는 것이 훨씬 빠르고.. 2024. 2. 3.
[python] 백준 1103 게임 문제 해결 DFS를 써야한다는 것은 쉽게 파악할 수 있다. 다만 떨어질 때 까지 옮겨지는 횟수를 세는 것으로 숫자가 커질 수 있으므로 dp를 사용하여한다. 숫자가 커지면 거의 DP를 사용해야 하는 것 같다. 한번 방문한 곳을 또 방문할 수 있으면 사이클을 돌 수 있고 무한반복이 가능하므로 -1을 출력하면 된다. 그렇지 않으면 떨어질 때 까지 혹은 방문한 지점이 나타날 때 까지 계속해서 DFS를 이용해서 나아가면 된다. CODE import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def dfs(sx, sy, cnt): global answer answer = max(answer, cnt) dxs = [1,-1,0,0] dys = [0,0,.. 2024. 1. 30.
[python] 백준 1939 중량제한 문제 해결 처음에 BFS를 이용해서 문제를 풀려했지만 메모리 초과가 났다. 그러면 que안에 적게 넣어서 통과하는지를 확인해야한다. 방법이 잘 안떠올라서 다른 풀이를 참고했고 이분 탐색을 이용해서 통과할 수 있는 최댓값이 나올때까지 계속 돌려보는 방법이 있었다. 처음에 최솟값 1 최댓값 1000000000을 잡은 후 mid = (low+high)//2를 잡고 mid가 통과하면 low를 한칸 올려주고 통과하지 못하면 high를 한칸 내려주며 계속 시도하는 방식이다. 이를 low 2024. 1. 29.
728x90