i can do ik!

BOJ 1758 알바생 강호

문제

스타박스는 손님을 입장시킬 때 독특한 방법으로 입장시킨다.

스타박스에서는 손님을 8시가 될 때 까지, 문앞에 줄 세워 놓는다. 

그리고 8시가 되는 순간 손님들은 모두 입구에서 커피를 하나씩 받고, 자리로 간다. 

강호는 입구에서 커피를 하나씩 주는 역할을 한다.

손님들은 입구에 들어갈 때, 강호에게 팁을 준다. 

손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다. 

각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다. 

만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다.

예를 들어, 민호는 팁을 3원 주려고 했고, 재필이는 팁을 2원, 주현이가 팁을 1원 주려고 한 경우를 생각해보자.

민호, 재필, 주현이 순서대로 줄을 서있다면, 민호는 강호에게 3-(1-1) = 3원, 재필이는 2-(2-1) = 1원, 주현이는 1-(3-1) = -1원을 팁으로 주게 된다. 

주현이는 음수이기 때문에, 강호에게 팁을 주지 않는다. 따라서, 강호는 팁을 3+1+0=4원을 받게 된다.

스타박스 앞에 있는 사람의 수 N과, 각 사람이 주려고 생각하는 팁이 주어질 때, 손님의 순서를 적절히 바꿨을 때, 

강호가 받을 수 잇는 팁의 최댓값을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다.

N은 100,000보다 작거나 같은 자연수이다.

둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다.

팁은 100,000보다 작거나 같은 자연수이다.

출력

강호가 받을 수 있는 팁의 최댓값을 출력한다.

예제 입력 1

4
3
3
3
3

예제 출력 1

6

예제 입력 2

3
3
2
3

예제 출력 2

5

예제 입력 3

5
7
8
6
9
10

예제 출력 3

30

예제 입력 4

5
1
1
1
1
2

예제 출력 4

2

예제 입력 5

3
1
2
3

예제 출력 5

4

풀이

import sys

input = sys.stdin.readline
n = int(input())
tips = []
res = 0

for i in range(n):
    tips.append(int(input()))

tips.sort(reverse=True)

for i in range(n):
    if tips[i] - i>0:
        res += tips[i]-i

print(res)

BOJ 11497 통나무 건너뛰기

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 

그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 

남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다.

높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자.

이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다.

즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 

배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 

우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다.

이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 

둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

출력

각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오.

예제 입력 1

3
7
13 10 12 11 10 11 12
5
2 4 5 7 9
8
6 6 6 6 6 6 6 6

예제 출력 1

1
4
0

풀이

import sys

input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort()
    res = 0

    for i in range(2, n):
        res = max(res, abs(arr[i] - arr[i-2]))
    print(res)

BOJ 2628 종이자르기

문제

아래 <그림 1>과 같이 직사각형 모양의 종이가 있다.

이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 

가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다.

점선을 따라 이 종이를 칼로 자르려고 한다. 

가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다.

예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 

그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다. 

이때 가장 큰 종이 조각의 넓이는 30㎠이다.

입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 

가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.

입력

첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다.

가로와 세로의 길이는 최대 100㎝이다.

둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 

셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 

가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다.

입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다.

출력

첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 

단, 넓이의 단위는 출력하지 않는다.

예제 입력 1

10 8
3
0 3
1 4
0 2

예제 출력 1

30

풀이

x, y = map(int, input().split())
x_arr = [0, x] 
y_arr = [0, y] 
for _ in range(int(input())):
    xy, length = map(int, input().split())
    if xy == 0:
        y_arr.append(length)
    else:
        x_arr.append(length)
        
x_arr.sort() 
y_arr.sort()

res = 0
for i in range(1, len(x_arr)):
    for j in range(1, len(y_arr)):
        width = x_arr[i] - x_arr[i-1]
        height = y_arr[j] - y_arr[j-1]
        res = max(res, width * height) 

print(res)

BOJ 5800 성적통계

문제

한상덕은 이번에 중덕 고등학교에 새로 부임한 교장 선생님이다. 

교장 선생님으로서 첫 번째 일은 각 반의 수학 시험 성적의 통계를 내는 일이다.

중덕 고등학교 각 반의 학생들의 수학 시험 성적이 주어졌을 때, 최대 점수, 최소 점수, 점수 차이를 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 중덕 고등학교에 있는 반의 수 K (1 ≤ K ≤ 100)가 주어진다. 

다음 K개 줄에는 각 반의 학생수 N (2 ≤ N ≤ 50)과 각 학생의 수학 성적이 주어진다. 

시험 성적은 0보다 크거나 같고, 100보다 작거나 같은 정수이고, 공백으로 나누어져 있다.

출력

각 반에 대한 출력은 다음과 같이 두 줄로 이루어져 있다.

첫째 줄에는 "Class X"를 출력한다. X는 반의 번호이며 입력으로 주어진 순서대로 1부터 증가한다.

둘째 줄에는 가장 높은 점수, 낮은 점수, 성적을 내림차순으로 정렬했을 때 
가장 큰 인접한 점수 차이를 예제 출력과 같은 형식으로 출력한다.

예제 입력 1

2
5 30 25 76 23 78
6 25 50 70 99 70 90

예제 출력 1

Class 1
Max 78, Min 23, Largest gap 46
Class 2
Max 99, Min 25, Largest gap 25

풀이

k = int(input())

for i in range(k):
    student = list(map(int, input().split()))
    del student[0]
    student.sort()
    diff = []

    print('Class', i+1)
    
    for i in range(len(student)-1):
        diff.append(student[i+1] - student[i])

    print('Max', str(max(student))+',' ,'Min', str(min(student))+',', 'Largest gap', max(diff))

BOJ 1940 주몽

문제

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 

그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 

야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 

갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 

야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 

이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 

몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 

그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 

그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 

고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

예제 입력 1

6
9
2 7 4 1 5 3

예제 출력 1

2

풀이

n = int(input())
m = int(input())
nums = list(map(int, input().split()))
nums.sort()
cnt = 0
start = 0
end = n-1

while start < end:
    if nums[start] + nums[end] == m:
        cnt += 1
        start += 1
        end -= 1
    elif nums[start] + nums[end] < m:
        start += 1
    else:
        end -= 1
        
print(cnt)

BOJ 10817 세 수

문제

세 정수 A, B, C가 주어진다. 이때, 두 번째로 큰 정수를 출력하는 프로그램을 작성하시오. 

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

입력

첫째 줄에 세 정수 A, B, C가 공백으로 구분되어 주어진다. (1 ≤ A, B, C ≤ 100)

출력

두 번째로 큰 정수를 출력한다.

예제 입력 1

20 30 10

예제 출력 1

20

예제 입력 2

30 30 10

예제 출력 2

30

예제 입력 3

40 40 40

예제 출력 3

40

예제 입력 4

20 10 10

예제 출력 4

10

풀이

import sys

input = sys.stdin.readline
arr = list(map(int, input().split()))

arr.sort(reverse=True)

print(arr[1])

CodeUp 3004 데이터 재정렬

문제

프로그래밍 문제를 풀다 보면 뒤죽박죽인 N개의 데이터를 숫자의 크기 순으로 0 ~ N-1까지의 숫자로 재정렬 해야되는 경우가 종종 있다.

예를 들어 N=5 이고,

50 23 54 24 123

이라는 데이터가 있다면,

2 0 3 1 4

가 된다.

데이터를 재정렬하는 프로그램을 작성하시오.

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

입력

첫째 줄에 데이터의 개수 N이 입력된다. ( 1 <= N <= 50,000)

둘째 줄에 공백으로 분리되어 N개의 서로 다른 데이터가 입력된다. (값의 범위:0~500,000)

출력

N개의 데이터를 0 ~ N-1로 재정렬하여 출력하라.

입력 예시

5
50 23 54 24 123

출력 예시

2 0 3 1 4

도움말

50 23 54 24 123 에서

23, 24, 50, 54, 123 순서로 0, 1, 2, 3, 4 가 된다.

그리고 원래의 위치대로 출력한다.

풀이

n = int(input())
cnt = [0 for _ in range(500001)]
nums = list(map(int, input().split()))

for i in range(n):
    num = nums[i]
    cnt[num] += 1

for i in range(len(cnt)-1):
    cnt[i+1] += cnt[i]

for i in nums:
    print(cnt[i]-1, end = ' ')

CodeUp 1709 내림차순 정렬

문제

  데이터를 입력받아 내림차순으로 정렬하는 프로그램을 작성하시오.
  
  시간 제한 : 1 초
  메모리 제한 : 128 MB

입력

첫줄에는 데이터의 개수를 입력받는다.(100이하의 정수)

다음 줄에는 데이터가 입력된다.(100이하의 정수)

출력

정렬된 데이터가 출력된다.

입력 예시

7
51 44 81 1 9 12 25

출력 예시

81 51 44 25 12 9 1

풀이

n = int(input())
nums = list(map(int, input().split()))

nums.sort(reverse=True)

print(*nums)