둔필승총

www.acmicpc.net/problem/2805

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력 1

4 7

20 15 10 17

예제 출력 1

15

[문제 해설]

H높이보다 큰 것은 (높이 - H)가 될 것이고 높이보다 작으면 잘리지 않을 것이다. 적당한 H 높이를 찾는 방법인데 최적의 길이를 찾아야되기 때문에 요리조리 해보면서 구해야 된다. 최적의 수를 찾는 것이기 때문에 sorting하는 방법이다. 알고리즘은 binary_search를 사용해서 풀면 시간도 적절하게 나온다. 

import sys
sys.stdin.readline

n,m = map(int,input().split())
tree=list(map(int,input().split()))

start = 1
end = max(tree)
ans=0

while start<=end:
    mid=(start+end)//2
    result=0
    for i in tree:
        if mid<i:
            result+=i-mid
    if result>=m:
        ans=mid
        start=mid+1
    elif result<m:
        end=mid-1
print(ans)

www.acmicpc.net/problem/1026

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0]×B[0] + ... + A[N-1]×B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 S의 최솟값을 출력한다.

예제 입력 1

5

1 1 1 6 0

2 7 8 3 1

예제 출력 1

18

힌트

A를 {1, 1, 0, 1, 6}과 같이 재배열하면 된다.

[문제 해설]

일단 B에 있는 수들을 재배열하면 안되고 A에 있는 수들을 재배열하여 최솟값을 구해야 한다. B에 있는 수들 중 제일 큰 수에 A의 제일 작은 수를 배치하면 된다. 사실 B를 정렬하면 sort(reverse=True)를 통하여 A와 곱하면 되지만 조건에서 그렇게 하지 말라고 하였기 때문에 새로운 방법을 고안해야된다. 

A배열의 제일 작은 수와 B배열의 제일 큰 수를 곱해주고 이 제일 작은수와 제일 큰수는 빼주고 다시 sort해서 반복해 주면 된다. 

n = int(input())

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

s = 0
for i in range(n):
    s += min(a_list) * max(b_list)
    a.pop(a_list.index(min(a)))
    b.pop(b_list.index(max(b)))

print(s)

www.acmicpc.net/problem/10814

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

예제 입력 1

3

21 Junkyu

21 Dohyun

20 Sunyoung

예제 출력 1

20 Sunyoung

21 Junkyu

21 Dohyun

[문제 해설]

이 문제는 두 가지 조건이 있다. 먼저 나이순으로 정렬을 하고 그 다음 먼저 온 순서대로 정렬을 하면 된다. 

n = int(input())

data = []
for i in range(n):
    age, name = list(input().split())
    age=int(age)
    data.append((age, name, i))
data = sorted(data, key=lambda x: x[0])

for i in range(n):
    print(str(data[i][0]) + ' ' + data[i][1])

그리고 type에 따라 비교가 다르게 되기 때문에 나이는 int로 바꾸어서 계산해준다.

www.acmicpc.net/problem/1181

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

예제 입력 1

13

but

i

wont

hesitate

no

more

no

more

it

cannot

wait

im

yours

예제 출력 1

i

im

it

no

but

more

wait

wont

yours

cannot

hesitate

[문제 해설]

이 문제는 두 가지 해결해야 될 점이 있다. 먼저 길이가 짧은 순서대로 단어를 정렬해야 되고, 두 번째 그 정렬된 상태를 단어 사전 순서대로 정렬하면 된다. 두 가지 조건이 있으면 lambda 함수를 떠올려서 정렬하는 방법을 생각하면 된다.

그리고 중복을 제거해야 하기 때문에 set으로 바꾼뒤에 다시 list형식으로 바꾸어 준다.

n = int(input())
datas=[]
for _ in range(n):
    word = input()
    word_c = len(word)
    datas.append((word,word_c))
#중복 값 제거
datas=list(set(datas))

datas.sort(key=lambda word:(word[1],word[0]))

for i in range(len(datas)):
    print(datas[i][0])

www.acmicpc.net/problem/1931

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용 표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

11

1 4

3 5

0 6

5 7

3 8

5 9

6 10

8 11

8  12

2 13

12 14

예제 출력 1

4

[문제 해설]

출력에서 4는 힌트에 있듯이 (1,4), (5,7), (8,11), (12,14)을 이용한 경우이다. 배열에는 시작시간과 종료시간이 동시에 입력되어있고 동시에 고려해야 된다. 회의의 최대 개수를 구해야 한다. 파이썬 정렬을 다중 조건으로 하려고 할 때는 lambda함수를 사용하면 쉽게 할 수 있다.

#lambda함수

일반적으로 우리는 파이썬 내장 함수인 .sort() 또는 sorted()를 사용한다. 배열을 sort()를 이용하면 오름차순으로 바뀐다. 

sorted() 함수가 어떻게 작동하는지 자세히 살펴보자. 

data=[[1,2],[3,5],[3,4],[0,5],[1,7],[4,5]]
s_data=sorted(data)#[[0, 5], [1, 2], [1, 7], [3, 4], [3, 5], [4, 5]]

인자 없이 그냥 sorted()만 쓰면, 리스트 아이템의 각 요소 순서대로 정렬을 한다. key 인자를 함수에 넘겨주면 해당 함수의 반환 값을 비교하여 순서대로 정렬한다. 예를 들어 data의 첫 번째 요소로 정렬할 것인지, 두 번째 요소로 정렬할 것인지 정해줄 수 있다. 그리고 첫 번째 요소로 정렬하고 그다음 두 번째 요소로 정렬을 시도할 수도 있다.

data=[[1,2],[3,5],[3,4],[0,5],[1,7],[4,5]]
s_data=sorted(data) #[[0, 5], [1, 2], [1, 7], [3, 4], [3, 5], [4, 5]]
s2_data=sorted(data,key=lambda x:x[0])#[[0, 5], [1, 2], [1, 7], [3, 5], [3, 4], [4, 5]]
s3_data=sorted(data,key=lambda x:(x[0],x[1]))#[[0, 5], [1, 2], [1, 7], [3, 4], [3, 5], [4, 5]]

sorted()의 key의 인자로, 내가 정렬할 비교 함수를 넣어주면 된다. 비교 함수는 비교할 아이템의 요소를 반화하면 된다. lambda는 비교하는 익명 함수인 것이다. 

그럼 이 문제에서는 lambda함수를 사용할 수 있을까? 주어진 시작시간과 끝나는 시간들을 이용해서 가장 많은 회의의 수를 알기 위해서는 빨리 끝나는 회의 순서대로 정렬을 해야 한다. 빨리 끝날수록 뒤에서 고려해볼 회의가 많기 때문이다. 일단 시작 시간 기준으로 정렬을 하고 종료 시간 기준으로 정렬을 해준다. lambda함수를 사용해서 정렬한 뒤에 시작 시간이 제일 빠른 것을 저장해 둔 뒤 시작시간을 비교하여 만약 시작시간이 저장해둔 종료시간보다 크면 그 수업을 선택한 뒤 시작시간을 업데이트해준다. 코드는 다음과 같다.

n = int(input())
meeting=[]
for i in range(n):
    start,end= map(int,input().split())
    meeting.append((start,end))

#시작 시간 기준으로 정렬
meeting=sorted(meeting,key=lambda x:x[0])
#종료 시간 기준으로 정렬
meeting=sorted(meeting,key=lambda x:x[1])

start_time=0
result=0
for time in meeting:
    if time[0]>=start_time:
        start_time=time[1]
        result+=1

print(result)

www.acmicpc.net/problem/10989

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

10

5

2

3

1

4

2

3

5

1

7

예제 출력 1

1

1

2

2

3

3

4

5

5

7

[문제 해설]

 오름차순으로 n개의 수를 정렬하면 된다. 물론 배열에 저장해서 오름차순으로 정렬하는 방법을 맨 처음 떠올리겠지만 메모리가 8MB밖에 안된다는 것이 이 문제의 함정이다. 따라서 계수정렬을 이용하였다.

 계수정렬(Count Sort)알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 데이터의 개수가 N, 데이터 중 최댓값이 K일 떄, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다. 여기서 숫자의 크기가 10000보다 작기 때문에 계수정렬을 쓸 수 있는 것이다. 1부터 10000까지의 배열을 0으로 저장해두고 각 숫자가 나올때마다 크기를 1씩 증가시킨다. input을 받을때 같이 data에 숫자를 1씩 증가시키고 나중에 정답으로 출력시켜주면 된다.

import sys
input = sys.stdin.readline

n = int(input())
data=[0]*10001
for _ in range(n):
    num = int(input())
    data[num-1]+=1

for i in range(10000):
    if data[i]!=0:
        for j in range(data[i]):
            print(i+1)

www.acmicpc.net/problem/14501

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

예제 입력 1

7 3 10 5 20 1 10 1 20 2 15 4 40 2 200

예제 출력 1

45

예제 입력 2

10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10

예제 출력 2

55

예제 입력 3

10 5 10 5 9 5 8 5 7 5 6 5 10 5 9 5 8 5 7 5 6

예제 출력 3

20

예제 입력 4

10 5 50 4 40 3 30 2 20 1 10 1 10 2 20 3 30 4 40 5 50

예제 출력 4

90

[문제 해설]

 N+1일째 되는 날 퇴사를 한다. 그때까지 일을 제일 많이 하면 된다. 그렇다면 다이나믹 프로그래밍을 적용했을때, 마지막에 일하는 것이 어떤 것이냐에 따라 최대값이 어떤지 비교해주면 된다.

 각 날짜에 최대를 d라는 배열에 저장해두자. 그러면 d[i]는 어떤 값이 들어올까? 이 문제의 핵심은 뒤에서부터 다이나믹 프로그래밍을 적용해야 한다는 점이다. 조건중에 n+1에는 회사에 없기때문에 일을 할 수 없다. 그래서 먼저 i날에 일을 하는 기간인 t[i]를 더한값이 n을 넘으면 안된다. 넘는다면 그 날일을 건너뛰고 그 다음날 일을 찾는 것이다. 

 만약 i+t[i]가 n을 넘지 않을 경우에는 다음과 같이 된다. 

d[i] = max(p[i] + d[i + t[i]], d[i + 1])

뒤에서부터 반복문을 쓰면 되는 것이므로 n-1에서 n이 0이 될때까지 구하면 된다. 이를 식으로 쓰면 된다.

[정답]

n = int(input())
t = []
p = []
d = [0] * (n+1)
for i in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)
# d[i]=max(p[i]+d[i+t[i]],d[i+1]) 그 일을 하는경우,하지않고 다음날 일을 하는 경우
for i in range(n - 1, -1, -1):
    if i + t[i] >n:
        d[i] = d[i + 1]
    else:
        d[i] = max(p[i] + d[i + t[i]], d[i + 1])

print(d[0])

www.acmicpc.net/problem/9625

문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

입력

첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.

출력

첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.

예제 입력 1

1

예제 출력 1

0 1

[문제 해설]

문제 조건에서 A는 B로 변하고 B는 BA로 변한다는 사실에 입각해서 문제를 풀면된다. 결과적으로 A와 B의 개수를 구하면 되는 것이므로 K-1번 누르는 것과 K번 누르는 것의 차이를 구하면 된다. 

a는 k-1번의 b의 개수와 같다. b는 k-1번의 a의 개수와 b의 개수의 합과 같다. 

k = int(input())

a=[0]*46
b=[0]*46

a[0]=1

for i in range(1,k+1):
    a[i]=b[i-1]
    b[i]=a[i-1]+b[i-1]

print(a[k],b[k])