i can do ik!

BOJ 1715 카드 정렬하기

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 

각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 

이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 

이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 

예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 

합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 

그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 

(10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 

최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

시간 제한 : 2 초 
메모리 제한 : 128 MB

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 

숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

예제 입력 1

3
10
20
40

예제 출력 1

100

풀이

import heapq
import sys

input = sys.stdin.readline
n = int(input())
card = []

for _ in range(n):
    num = int(input())
    heapq.heappush(card, num)

res = 0

while len(card)>1:
    n1 = heapq.heappop(card)
    n2 = heapq.heappop(card)
    res += n1 + n2
    heapq.heappush(card, n1+n2)

print(res)

CodeUp 3321 : 최고의 피자

문제 설명

vega 선생님은 Miss 피자 가게의 단골 손님이다.

그는 이번 달부터 절약 생활을 시작했다.

그래서 그는 피자 가게에서 주문할 수 있는 피자 중 1 달러 당 열량이 최대가 되는 피자를 주문하고 싶어한다.

이러한 피자를 "최고의 피자"라고 부르기로 하자.

"최고의 피자"는 1종류가 아니다.

Miss 피자는 N 종류의 토핑에서 여러 종류를 자유롭게 선택하여, 도우 위에 올려 주문할 수있다.

같은 토핑을 2 개 이상 올릴 수 없다.

도우에 토핑을 하나도 하지 않은  피자도 주문할 수있다.

도우의 가격은 A 달러이며, 토핑의 가격은 모두 B 달러이다.

실제 피자 가격은 도우의 가격과 토핑 가격의 합계이다.

즉, 토핑을 k 종류 (0 ≦ k ≦ N) 한 피자의 가격은 A + k × B 원이다.

피자 전체의 칼로리는 도우 열량과 토핑 칼로리의 합계이다.

도우의 가격과 토핑의 가격, 그리고 도우와 각 토핑 열량 값이 주어 졌을 때, 

"최고의 피자"의 1 달러 당 열량의 수를 구하는 프로그램을 작성하시오.

시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

첫 번째 줄에는 토핑 종류 수를 나타내는 하나의 정수 N (1 ≦ N ≦ 100)이 입력된다.

두 번째 줄에는 두 개의 정수 A, B (1 ≦ A ≦ 1000,1 ≦ B ≦ 1000)가 공백을 구분으로 입력된다. 

A는 도우의 가격, B는 토핑의 가격을 나타낸다.

세 번째 줄에는 도우의 칼로리를 나타내는 정수 C (1 ≦ C ≦ 10000)가 입력된다.

3 + i 행 (1 ≦ i ≦ N)는 i 번째의 토핑 칼로리 수를 나타내는 정수 Di (1 ≦ Di ≦ 10,000)가 입력된다.

출력

"최고의 피자" 1 달러 당 열량의 수를 소수점 이하는 버리고 정수로 출력한다.

입력 예시

3
12 2
200
50
300
100

출력 예시

37

풀이

n = int(input())
a, b = map(int, input().split())

c = int(input())
tp_list = []
for i in range(n) :
    tp_list.append(int(input()))

tp_list.sort(reverse=True)

res = 0 
price = 0
cal = 0

for i in tp_list :
    cal += i
    price += b
    tmp=(c+cal)/float(a+price)

    if res>tmp:
        break
    else:
        res=tmp

print(int(res))

CodeUp 3301 : 거스름돈

문제 설명

어떤 가게의 욕심쟁이 점원은 거스름돈을 나눠줄때 거스름돈의 개수를 적게해서 주고자 한다.

거스름돈을 입력 받아 점원이 줄 수 있는 최소 거스름돈의 개수를 출력하시오.

예를 들어 54520원인 경우,

거스름돈으로 50000원권 1장, 1000원권 4장, 500원 1개, 10원 2개 해서 총 8개이다.

(※ 현재 우리나라가 사용하고 있는 화폐를 사용한다. 10원 50원 100원 500원 1,000원 5,000원 10,000원 50,000원)

시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

거스름돈 n이 입력된다. ( n은10이상의  int 범위 )

출력

최소 거스름돈의 개수를 출력한다.

입력 예시

54520

출력 예시

8

풀이

N = int(input())

money = [50000, 10000, 5000, 1000, 500, 100, 50, 10]
cnt = 0
for i in money :
    cnt += N // i
    N %= i

print(cnt)

CodeUp 2001 : 최소 대금

문제 설명

파파 파스타 가게는 점심 추천 파스타와 생과일 쥬스 세트 메뉴가 인기가 좋다.

이 세트 메뉴를 주문하면 그 날의 3 종류의 파스타와 2 종류의 생과일 쥬스에서 하나씩 선택한다.

파스타와 생과일 쥬스의 가격 합계에서 10%를 더한 금액이 대금된다.

어느 날의 파스타와 생과일 쥬스의 가격이 주어 졌을 때, 그 날 세트 메뉴의 대금의 최소값을 구하는 프로그램을 작성하라.

시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

입력은 5 행으로 이루어지며, 한 줄에 하나씩 양의 정수가 적혀있다.

1행의 정수는 첫 번째 파스타 가격이다.

2행의 정수는 두 번째 파스타 가격이다.

3행의 정수는 세 번째 파스타 가격이다.

4행의 정수는 첫 번째 생과일 쥬스 가격이다.

5행의 정수는 두 번째 생과일 쥬스의 가격이다.

(모든 파스타와 생과일 쥬스의 가격은 100 원이상 2000원 이하이다.)

출력

그날 세트 메뉴의 최소 대금을 소수 첫째자리까지 출력하시오.

입력 예시

800
700
900
198
330

출력 예시

987.8

풀이

pasta = []
juice = []

for i in range(3) :
    pasta.append(int(input()))

for i in range(2) :
    juice.append(int(input()))

res = (min(pasta) + min(juice)) * 1.1

print(f'{res:.1f}')

BOJ 2847 게임을 만든 동준이

문제

학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 

게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 

플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 

동준이는 레벨을 난이도 순으로 배치했다. 

하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다.

이 문제를 해결하기 위해 동준이는 특정 레벨의 점수를 감소시키려고 한다. 

이렇게해서 각 레벨을 클리어할 때 주는 점수가 증가하게 만들려고 한다.

각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램을 작성하시오. 

점수는 항상 양수이어야 하고, 1만큼 감소시키는 것이 1번이다. 항상 답이 존재하는 경우만 주어진다. 

정답이 여러 가지인 경우에는 점수를 내리는 것을 최소한으로 하는 방법을 찾아야 한다.

시간 제한 : 1 초
메모리 제한 : 128 MB

입력

첫째 줄에 레벨의 수 N이 주어진다. 

(1≤ N ≤ 100)다음 N개 줄에는 각 레벨을 클리어하면 얻는 점수가 첫 번째 레벨부터 마지막 레벨까지 순서대로 주어진다. 

점수는 20,000보다 작은 양의 정수이다.

출력

첫째 줄에 점수를 몇 번 감소시키면 되는지 출력한다.

예제 입력 1

3
5
5
5

예제 출력 1

3

예제 입력 2

4
5
3
7
5

예제 출력 2

6

풀이

import sys
input = sys.stdin.readline
n = int(input())
levels = [int(input()) for _ in range(n)]
cnt = 0

for i in range(n-1, 0, -1) :
    if levels[i] <= levels[i-1] :
        cnt += (levels[i-1] - levels[i]) + 1 
        levels[i-1] = levels[i] - 1

print(cnt)

BOJ 1783 병든 나이트

문제

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 

병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 

병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 

이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. 

N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

예제 입력 1

100 50

예제 출력 1

48

예제 입력 2

1 1

예제 출력 2

1

예제 입력 3

17 5

예제 출력 3

4

예제 입력 4

2 4

예제 출력 4

2

예제 입력 5

20 4

예제 출력 5

4

풀이

n, m = map(int, input().split())
res = 0
if n == 1 :
    res = 1
elif n == 2 :
    res = min(4, (m+1)//2)
elif m < 7 :
    res = min(4, m)
else :
    res = m-2

print(res)

BOJ 1449 수리공 항승

문제

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 

항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 

항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 

항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 

테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 

둘째 줄에는 물이 새는 곳의 위치가 주어진다. 

N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

예제 입력 1

4 2
1 2 100 101

예제 출력 1 

2

예제 입력 2

4 3
1 2 3 4

예제 출력 2

2

예제 입력 3

3 1
3 2 1

예제 출력 3

3

풀이

N, L = map(int, input().split())
hole = list(map(int, input().split()))

hole.sort()

start = hole[0]
end = hole[0] + L
cnt = 1

for i in range(N) : 
    if start <= hole[i] < end :
        continue
    else :
        start = hole[i]
        end = hole[i] + L
        cnt += 1

print(cnt)

BOJ 1439 뒤집기

문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 

다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 

다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 

뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.

2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
   하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 
   1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

시간 제한 : 2 초 
메모리 제한 : 128 MB

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

예제 입력 1

0001100

예제 출력 1 

1

예제 입력 2

11111

예제 출력 2

0

예제 입력 3

00000001

예제 출력 3

1

예제 입력 4

11001100110011000001

예제 출력 4

4

예제 입력 5 

11101101

예제 출력 5

2

풀이

S = input()
zero_cnt = 0
one_cnt = 0

if S[0] == '0' :
    zero_cnt += 1
else :
    one_cnt += 1

for i in range(len(S)-1) :
    if S[i] != S[i+1] :
        if S[i+1] == '0' :
            zero_cnt += 1
        elif S[i+1] == '1' :
            one_cnt += 1

print(min(zero_cnt, one_cnt))