BAEKJOON (Python)/Greedy Algorithm 11

BAEKJOON_1455 "뒤집기 II" PYTHON

[백준] 1455번 Python 파이썬 https://www.acmicpc.net/problem/1455 1455번: 뒤집기 II 세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다. 동전의 앞면을 0이라고 하고 뒷면을 1이라고 www.acmicpc.net Greedy Algorithm을 이용하여 푸는 문제이다. 입력받은 행렬의 앞쪽부터 변경할 경우, 뒤쪽을 바꾸면서 앞쪽이 또 바뀔 수 있기 때문에 뒤쪽의 수부터 바꾸어 준다. n, m = map(int, input().split()) lst = [] result = 0 for _ in range(n): a = list(map(int, input().rstr..

BAEKJOON_14916 "거스름돈" PYTHON

[백준] 14916번 Python 파이썬 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 거스름돈을 남겨줄 수 없는 경우는 n이 1이거나 3일 때이다. n을 5로 나누고 남은 나머지가 홀수라면 다시 나머지에 5를 더하고 2로 나누어 주고, 5로 나누고 남은 나머지가 짝수라면 바로 2로 나누어준다. coin = [5, 2] n = int(input()) count = 0 if n == 1 or n == 3: print(-1) else: count = n // 5 n = n % 5 if n % 2 != 0: count = count - 1 n = n + 5 print..

BAEKJOON_2720 "세탁소 사장 동혁" PYTHON

[백준] 2720번 Python 파이썬 https://www.acmicpc.net/problem/2720 2720번: 세탁소 사장 동혁 각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다. www.acmicpc.net 그리디 알고리즘의 대표 예시로 자주 나오는 최소 동전 갯수로 거스름돈을 주는 문제였다. import sys n = int(sys.stdin.readline()) money = [25, 10, 5, 1] result = [] for i in range(n): re = int(sys.stdin.readline()) for j in range(4): result.append(str(re // money[j])) re = re % mo..

BAEKJOON_1931 "회의실 배정" PYTHON

[백준] 1931번 Python 파이썬 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의가 시작하는 시간을 기준만 생각하여 문제를 풀었더니 틀렸다는 결과가 나왔다. import sys n = int(sys.stdin.readline()) conf = [] for _ in range(n): info = list(map(int, sys.stdin.readline().split())) conf.append(info) conf.sort() start = conf[0][1] count = 1 for i in range(1, n): if start ..

BAEKJOON_1449 "수리공 항승" PYTHON

[백준] 1449번 Python 파이썬 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 처음에 오름차순 정렬을 해주지 않아서 틀렸다. 예제 입력 3을 보고 오름차순 정렬을 해주었더니 정답 처리가 되었다! n, l = map(int, input().split()) location = list(map(int, input().split())) location.sort() # 입력 받은 위치들을 오름차순 정렬 해준다. pl = loca..

BAEKJOON_2839 "설탕 배경" PYTHON

[백준] 2839번 Python 파이썬 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net n = int(input()) count = 0 while True: if n % 5 == 0: count += n // 5 print(count) break n -= 3 count += 1 if n < 0: print(-1) break 혼자 공부하며 올리는 블로그입니다. 틀린 내용은 댓글 남겨주시면 감사하겠습니다.

BAEKJOON_1715 "카드 정렬하기" PYTHON

[백준] 1715번 Python 파이썬 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 힙(heap) 이란 '부모 노드가 자식보다 작거나 같은 값을 갖는 이진트리'이다. 이번 문제에서 가장 오래 걸린 부분이 heapify() 함수를 사용하지 않아서 발생한 오류를 찾는 것이 오래 걸렸다. 이미 값이 들어있는 리스트를 사용하기 때문에 heapify() 함수로 리스트를 힙으로 변환해주어야 한다. import sys, heapq n = ..

BAEKJOON_1049 "기타줄" PYTHON

[백준] 1049번 Python 파이썬 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net import sys n, m = map(int, sys.stdin.readline().split()) a_list = [] b_list = [] for i in range(m): a, b = map(int, sys.stdin.readline().split()) a_list.append(a) b_list.append(b) amin = min(a_list) ..

BAEKJOON_1789 "수들의 합" PYTHON

[백준] 1789번 Python 파이썬 https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 이 문제에서 N의 최대값을 구하려면 작은 수들을 더하여 S를 만들어야한다. s를 입력받아 s가 1인 경우와 1이 아닌 경우로 나누어 문제를 해결하였다. 아래 코드의 경우 시간 복잡도가 O(sqrt(s)) 이고, 입력이 클 수록 복잡도가 증가한다. s = int(input()) result = 0 for i in range(1, s + 1): if s == 1: result = 2 break else: s -= i result += 1 if s < 0: break print(r..