목록알고리즘 풀이/백준 알고리즘 (30)

보물창고 블로그

백준 알고리즘 1038번 감소하는 수 풀이 With Python

문제 링크: www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 �� www.acmicpc.net 문제는 N번째 감소하는 수를 구하는 것입니다. 처음에 이 문제를 보면 상당히 막막하지만, 천천히 생각해보면 의외로 간단합니다. 저는 1 자릿수부터 10 자릿수까지(9876543210) 천천히 숫자를 만들고 이때마다 count 수를 늘려서 count수가 N과 같아질 때 감소하는 수를 출력하도록 하였습니다. 파이썬으로 해결한 코드는 아래와 같습니다. import sys n = int..
알고리즘 풀이/백준 알고리즘 2020. 9. 9. 22:42
백준 알고리즘 12869번 뮤탈리스크 풀이 With Python

문제 링크: www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 저는 SCV의 개수에 따라 CASE분류를 통하여 문제를 해결하였습니다. 먼저 SCV수가 1마리일 경우 SCV체력을 9로 나누어 나머지가 0일 경우 몫을 출력하고 아닐 경우 몫+1의 값을 출력하였습니다. SCV가 2마리 이상일 경우에는 DFS(깊이 우선 탐색)으로 문제를 해결하였습니다. 만약 현재 최소의 횟수보다 같거나 높아진다면 분기하지 않는 백 트레킹을 사용하였고, 한 번만 탐색한 것을 체크하기 위해 SC..
알고리즘 풀이/백준 알고리즘 2020. 9. 2. 18:02
백준 알고리즘 12865번 평범한 배낭 풀이 With Python

문제 링크: https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 대표적인 DP(다이내믹 프로그래밍) 문제입니다. 소스 코드는 아래와 같습니다. 재귀는 쓰지 않았습니다. import sys n, k = map(int, sys.stdin.readline().split()) cost = [[0] * (k + 1) for _ in range(n + 1)] backpack = [l..
알고리즘 풀이/백준 알고리즘 2020. 7. 17. 16:42
백준 알고리즘 9095번 1, 2, 3 더하기 풀이 With Python

문제 링크: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net 문제를 해결하기 위해서는 점화식을 세워야 합니다. 제가 세운 점화식은 다음과 같습니다. 먼저 정수 n>=4라는 가정하에 정수 n을 1,2,3의 합으로 나타내는 방법은 정수 n-1을 나타내는 방법에 1을 더하는 방법과 정수 n-2를 나타내는 방법에 2를 더하는 방법과 정수 n-3을 나타내는 방법에 3을 더하는 방법이..
알고리즘 풀이/백준 알고리즘 2020. 7. 7. 16:56
Prev 1 2 3 4 ··· 8 Next