둔필승총

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])

www.acmicpc.net/problem/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

[문제 해설]

 1로 만들기는 다이나믹 프로그래밍의 대표적인 예이다. 1로 만드는 3가지 방법은 3으로 나누기, 2로 나누기, 1 빼기 이다. 어떤 것이 연산을 더 적게 할 수 있는지 생각하면 된다. 

 먼저 d 배열은 만든다. d 배열은 각각의 input n에서 최소의 값을 저장한 배열이다. n은 1보다 크기 때문에 반복문은 2부터 n까지 돌린다. 먼저 d[i]는 d[i-1] +1은 1빼는 것이므로 먼저 저장해두고 비교한다. 비교할 것은 3으로 나누는 것과 2로 나누는 것을 비교해주면 된다. 

3으로 나누어 떨어진다고 하면 d[i] = d[i//3] + 1 이다. 1을 더해주는 것은 3으로 나누는 연산을 해주었기 때문이다. 그럼 1을 빼는 것이 연산을 더 줄일 수 있는지 3으로 나누는 것이 더 줄일 수 있는지 구한다. 이 식이 바로

d[i]=min(d[i//3]+1, d[i])

 이다. 2로 나누는 것도 똑같이 해주면 된다.

# 1로 만들기
import sys
input = sys.stdin.readline

n = int(input())

d = [0]*1000002

for i in range(2,n+1):
    d[i] = d[i - 1] + 1
    if i%3==0:
        d[i]=min(d[i//3]+1, d[i])
    if i%2==0:
        d[i]=min(d[i//2]+1, d[i])

print(d[n])

www.acmicpc.net/problem/2579

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력 1 복사

6 10 20 15 25 10 20

예제 출력 1 복사

75

[문제 해설]

일단.acmicpc.net/problem/2579

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.



예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.



계단 오르는 데는 다음과 같은 규칙이 있다.

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력 1 복사

6 10 20 15 25 10 20

예제 출력 1 복사

75

[문제 해설]

 일단 최대값을 구해야 된다는 사실을 알 수 있다. max()를 쓸 생각을 하고 있자.

계단을 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 그래서 생각할 수 있는게

r[i]의 경우에 r[i-2]에 마지막 계단을 밟는 경우와 r[i-1]의 경우에서 마지막 계단을 밟는 경우 2개 중 어느게 최대값인지 계산하면 된다고 생각했다.

 근데, 연속된 세 개의 계단을 모두 밟아서는 안된다는 조건이 있다. r[i-1]의 경우에서 마지막 계단을 밟는 경우가 연속된 세 개의 계단을 밟은것인지 아닌지 확신할 수 없다.

 그래서 r[i-3]까지 생각해야된다. 그래서 r[i]는 r[i-2]+d[i] (여기서 d[i]는 i번째 계단의 점수)와 r[i-3]+ d[i-1] + d[i] 중 최대값을 구하면 된다.

 그리고 초기값 n이 0일때는 0, n이 1일 때는 계단 첫번째 값 (d[0]), n이 2일 때는 d[0]+d[1]이 된다. 

n = int(input())
d = []
r = [0] * n
for _ in range(n):
    d.append(int(input()))

if n==0:
    print(0)
elif n==1:
    print(d[0])
elif n==2:
    print(d[0]+d[1])
else:
    r[0] = d[0]
    r[1] = d[0] + d[1]
    r[2] = max(d[0] + d[2], d[1] + d[2])

    for i in range(3, n):
        r[i] = max(r[i - 2] + d[i], r[i - 3] + d[i - 1] + d[i])

    print(r[n - 1])