본문 바로가기
728x90

알고리즘316

[python] 백준 2092 집합의 개수 https://www.acmicpc.net/problem/2092 2092번: 집합의 개수 1부터 T까지의 범위에 있는 수들이 총 A개 있다. 이들 중 K개를 골라서 집합을 만들 때, 가능한 집합의 개수를 세려 한다. 단, K의 범위는 1 ≤ S ≤ K ≤ B ≤ A로 한다. 즉, 두 정수 S, B를 입력받아서 www.acmicpc.net 문제 해결 각 숫자의 개수를 알 수 있도록 numbers[num]을 통해 개수를 저장한다. dp[i][j] 를 i까지 숫자중 j개 사용했을 때 가지수를 나타내는 dp함수를 만든다 기본적으로 숫자 i가 k개 있을 때 k개이하를 쓸 수 있으므로 dp[i][j] += 1씩 해준다. (j=k 일때 dp[i][j] += dp[i-1][j-k]이다. 숫자를 1000000으로 나눠.. 2024. 2. 9.
[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.
728x90