본문 바로가기

공부하는 것들

(52)
백준 13417번: 카드 문자열(그리디) https://www.acmicpc.net/problem/13417 13417번: 카드 문자열 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처 www.acmicpc.net import sys def solve(cards): dict_alphabet = {chr(i):i for i in range(65,65+27)} reverse_alphabet = {i:chr(i) for i in range(65,65+27)} cards_int = [dict_alphabet[c] for c in cards] arange = [] for card in cards_int: if ara..
백준 12845번: 모두의 마블 https://www.acmicpc.net/problem/12845 12845번: 모두의 마블 영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다. 이번 이 www.acmicpc.net 무조건 처음의 가장 큰 레벨을 가진 숫자에 합치는 게 유리함. def solve(cards): cards = sorted(cards, reverse = True) golds = 0 while len(cards)>=2: golds = golds + cards[0]+cards[1] del cards[1] return golds if __name__=='__main__': N = int(input()) ..
백준 3061번: 사다리 https://www.acmicpc.net/problem/5545 5545번: 최고의 피자 상근이는 근처 피자 가게에서 매일 저녁으로 피자를 배달해 먹는다. 주머니 사정이 얇아진 상근이는 이번 달부터는 "최고의 피자"를 구매하려고 한다. 최고의 피자란, 피자 가게에서 주문할 수 www.acmicpc.net 이 피자 가게는 토핑 N개에서 여러 종류를 선택해서 주문할 수 있다. 같은 종류의 토핑을 2개 이상 선택할 수는 없다. 또, 토핑을 전혀 선택하지 않을 수도 있다. 도우의 가격은 A원이고, 토핑의 가격은 모두 B원이다. 피자의 가격은 도우와 토핑의 가격의 합계가 된다. 즉, 토핑을 k종류 (0 ≤ k ≤ N) 선택했다면, 피자의 가격은 A + B*k원이 된다. def solve(A,B, A_cal, B..
백준 2872번 : 우리집엔 도서관이 있어(그리디) *** https://www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근 www.acmicpc.net 사전 순으로 가장 앞서는 책은 가장 위에 놓고, 가장 뒤에 있는 책은 가장 밑에 놓아야 한다. 책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다. 현재 책이 어떻게 쌓여있는지가 주어졌을 때, 몇 번만에 사전 순으로 쌓을 수 있는지 구하는 프로그램을 작성하시오. 예시: (2, 4, 3, 1) --> ( 3, 2, 4, 1) --> (2, 3, 4, 1) -->..
백준 2012번: 등수 매기기 **(그리디) https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 실제 등수가 A인데 B로 예상한 만큼 abs(A-B)만큼으로 불만도 수치화. 불만도의 합을 최소로 하는 프로그램을 작성하시오. import sys def solve(N, rankings): rankings = sorted(rankings) basic = list(range(1,N+1)) ans = 0 for i in range(N): ans += abs(basic[i]-rankings[i]) return..
백준 1448번 : 삼각형 만들기 (그리디)** https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net N 개의 빨대 중에 3개의 빨대를 선택해서 삼각형을 만들었을 때, 세 변의 길이의 합이 최대가 되도록. (삼각형을 못 만들 경우 -1) INPUT: 빨대 갯수, 빨대의 길이 OUTPUT: 삼각형 세 변의 길이의 합의 최댓값. 삼각형이 성립 안 될 경우 -1 ## 백만이면 포문 한번만 돌아야 하나봄 https://2ssue.github.io/Algorithm/docs/baek..
백준 20363번 : 당근 키우기(그리디) https://www.acmicpc.net/problem/20363 20363번: 당근 키우기 첫째 줄에 X와 Y (0 ≤ X, Y ≤ 109)를 의미하는 정수가 공백으로 구분되어 주어진다. www.acmicpc.net 문제 요약: 씨앗이 X 온기, Y 수분을 가지면 당근으로 자란다. 햇빛 1 --> 온기 +1, 햇빛 10 --> 수분 -1, 물 10 --> 온기 -1 온기와 수분은 음수가 되지 않고, 초기값은 둘 다 0 INPUT : 당근이 되는 데 필요한 온기 X, 수분 Y OUTPUT : 햇빛과 물을 주는 횟수의 합의 최솟값 문제 풀이 : 이건 그리디로 분류돼있긴 한데, 수학적인 접근이 더 큰 것 같다. def solve(N,M): MM = max(N,M) mm = min(N,M) return MM..
백준 20937번: 떡국(그리디) https://www.acmicpc.net/problem/20937 20937번: 떡국 Naver D2를 아시나요? D2는 For Developers, By Developers의 약자로, 개발자들을 위해 개발자들이 직접 만들어 가고 있는 네이버 개발자 지원 프로그램입니다. 네이버가 축적한 기술과 지식을 공유하고, 외 www.acmicpc.net INPUT: N개의 떡국 그릇을 제공 // 떡국 그릇의 크기(정수) OUTPUT: 쌓을 수 있는 최소 그릇탑의 갯수 그릇의 크기가 더 큰 것 위에만 작은 것을 올릴 수 있음. 탑의 갯수가 최소라는 것은, 최대한 높이 쌓았을 때 가능함. def solve(N, items): items = sorted(items, reverse = True) cnt = 0 tops ..