[파이썬] 백준 15652 : N과 M(4)

[파이썬] 백준 15652 : N과 M(4) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 실버 3 백트래킹 접근 중복된 순열을 구하는 간단한 문제. 파이썬은 itertools 라이브러리의 combinations_with_replacement 를 이용하면 쉽게 중복 순열을 구할 수 있다. 코드 from itertools import combinations_with_replacement import sys N, M = map(int, sys...

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 8.
• textsms

[파이썬] 백준 1789 : 수들의 합

[파이썬] 백준 1789 : 수들의 합 https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 실버 5 그리디 알고리즘, 수학 접근 N개의 자연수의 합이 입력한 값과 같을때, N의 최댓값을 구하는 문제이다. 이때 N개의 자연수는 전부다 다른 값을 가져야 한다. 합을 이루고 있는 자연수들이 최대가 되기 위해서는 값이 작을수록 좋을 것이다. 200을 입력했다면 1+2+3+4+5...로 계속해서 합산을 해주고, 200을 몇번째로 넘어가는지 확인하면 될 것이다. 코드 S = int(input()) sum = 0 N = 0 for i in range(1, S+1): sum +=..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 8.
• textsms

[파이썬] 백준 1931 : 회의실 배정

[파이썬] 백준 1931 : 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 실버 2 그리디 알고리즘, 정렬 접근 회의 시작 시간, 끝나는 시간이 모두 빠르면 빠를수록 가능한 회의의 개수가 많아진다. 예를 들어, 1~4시에 끝나는 회의 다음으로 올 수 있는 것은 4시와 같거나 큰 회의 시간뿐이다. 또한, 회의 시간이 가장 먼저 끝나는 회의는 반드시 겹치지 않는 회의에 포함된다. (겹치지 않는 회의의 최대 개수를 구하므로) 회의가 끝나는 시간을 기준으로 오름차순 정렬을 하면 처음 회의를 기준으로 다음 회의의 시작시간이 겹칠 수 있는지 없는지에 대한 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 8.
• textsms

[파이썬] 백준 11399 : ATM

[파이썬] 백준 11399 : ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 실버 3 그리디 알고리즘, 정렬 접근 3 1 4 3 2를 2 5 1 4 3 순서로 접근한다는 것은 오름차순으로 접근하는 것과 같다. 코드 풀이(124ms) import sys input = sys.stdin.readline N = int(input()) nlst = sorted(list(map(int, input().split()))) S = 0 for i in range(N): for j..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 5.
• textsms

[파이썬] 백준 11047 : 동전 0

[파이썬] 백준 11047 : 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 실버 3 그리디 알고리즘 접근 실버 3이라 하기에는 쉬운 문제였다. 아무래도 그리디 알고리즘 문제가 전반적으로 구현 난이도가 쉬운 편이라서 그런 듯. 반복문을 거꾸로 돌리는 방법으로 동전의 단위를 큰 순서대로 순회할 수 있다. 해당 동전이 만들려는 K원보다 클경우는 다음 동전 단위로 차례를 넘기..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 5.
• textsms

[파이썬] 백준 2217 : 로프

[파이썬] 백준 2217 : 로프 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 실버 4 수학, 그리디 알고리즘, 정렬 접근 최대 중량이 각각 10, 15인 로프가 들 수 있는 물체의 최대 중량은 10x2 = 20이다. 15가 최대인 밧줄은 15를 들 수 있지만 10이 최대인 밧줄은 10까지 밖에 들 수 없다. 따라서 10 밧줄을 기준으로 생각한다면 10x2 = 20이 들 수 있는 최대 중량이며, 15 밧줄을 기준으로 생각한다면 15..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 5.
• textsms