본문 바로가기

알고리즘60

[Python] 백준 1398: 동전문제 https://www.acmicpc.net/problem/1398 1398번: 동전 문제 김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에 www.acmicpc.net 1. 10^K인 동전과 25*100^K 동전이 있는데 값은 10^15보다 작거나 같은 자연수이므로 1, 10, 25, 100, 1000, 2500, 10000, 100000,...로 10^15 이하까지 반복된다 2. 근데 계속보면 1, 10, 25의 값에 100씩 곱해지는 동전이 반복되는 것을 알 수 있다. (1, 10, 25), (100, 1000, .. 2021. 9. 27.
[Python] 백준 2590: 색종이 https://www.acmicpc.net/problem/2590 2590번: 색종이 과 같이 정사각형 모양을 한 여섯 종류의 색종이가 있다. 1번 색종이는 한 변의 길이가 1cm이고, 차례대로 그 길이가 1cm씩 커져, 6번 색종이의 한 변의 길이는 6cm가 된다. 주어진 색 www.acmicpc.net 1. 길이가 6일때는 갯수만큼 채워준다. 2. 길이가 5일때 1개 나머지는 길이가 1로 채워준다. 3. 길이가 4일때 1개 나머지는 길이가 2의 갯수만큼(max:5) 나머지는 길이가 1로 채워준다. 4. 길이가 3일때 남은 갯수가 4개이상이면 4개씩 채워주고 남은 갯수가 3개이면 길이가 2의 갯수(max:1) 나머지는 길이가 1로 채워준다. 남은 갯수가 2개이면 길이가 2의 갯수(max:3) 나머지는 .. 2021. 9. 26.
[Python] 백준 13975: 파일 합치기 3 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 1. 파일은 어차피 n-1번 합쳐야 한다. 2. 그러므로 가장 작은 파일 2개씩 파일이 1개가 남을 때까지 더해주면 된다. from heapq import heappush, heappop, heapify T = int(input()) while T: T -= 1 n = int(input()) f = list(map(int, input().split())) ans = 0 heapify(f) wh.. 2021. 9. 26.
[Python] 백준 2513: 통학버스 https://www.acmicpc.net/problem/2513 2513번: 통학버스 첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2 ≤ N ≤ 30,000이다. 두 번째 정수 K는 1 ≤ K ≤ 2,000이며, 통학버스의 정원 www.acmicpc.net 1. 학교를 기준으로 왼쪽 오른쪽을 나누어준다. (어차피 학교로 다시 돌아오면 현재 버스 인원이 0명이 되기 때문) 2. 최대힙을 이용하여 거리가 먼순으로 버스에 태운다. (가까운 곳을 우선으로 하면 1 번가 야할 먼 곳을 2번 갈경우도 생기기때문) 3. 현재 버스 인원 + 다음에 가야 할 아파트 인원이 최대를 넘을 경우 학교에 내려다 주고 다시 간다. from he.. 2021. 9. 25.

티스토리툴바