i can do ik!

BOJ 1339 단어 수학

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 

이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다.

같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때,

A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

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

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 

둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 

단어는 알파벳 대문자로만 이루어져있다. 

모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 

서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

예제 입력 1

2
AAA
AAA

예제 출력 1

1998

예제 입력 2

2
GCF
ACDEB

예제 출력 2

99437

예제 입력 3

10
A
B
C
D
E
F
G
H
I
J

예제 출력 3

45

예제 입력 4

2
AB
BA

예제 출력 4

187

풀이

import sys

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

for i in range(n): 
    s.append(list(input().strip()))

a = [0 for i in range(26)]

for i in s:
    li = len(i)
    for j in range(li):
        a[ord(i[j]) - 65] += 10 ** (li - j - 1)

a.sort(reverse=True)
res = 0
cnt = 9

for i in a:
    res += cnt * i
    cnt -= 1

print(res)

BOJ 1343 폴리오미노

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다.

이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

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

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

예제 입력 1

XXXXXX

예제 출력 1

AAAABB

예제 입력 2

XX.XX

예제 출력 2

BB.BB

예제 입력 3

XXXX....XXX.....XX

예제 출력 3

-1

예제 입력 4

X

예제 출력 4

-1

예제 입력 5

XX.XXXXXXXXXX..XXXXXXXX...XXXXXX

예제 출력 5

BB.AAAAAAAABB..AAAAAAAA...AAAABB

풀이

board = input()
board = board.replace("XXXX", "AAAA")
board = board.replace("XX", "BB")

if 'X' in board:
    print(-1)
else:
    print(board)

BOJ 13904 과제

문제

웅찬이는 과제가 많다. 

하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다.

과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 

웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

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

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다.

d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력 1

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

예제 출력 1

185

힌트

예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

풀이

import sys

input = sys.stdin.readline
n = int(input().rstrip())
arr = []
res = [0 for _ in range(1000)]

for i in range(n):
    a, b = map(int, input().split())
    arr.append([a, b])

arr.sort(reverse= True, key = lambda x : x[1])

for i in range(n):
    for j in range(arr[i][0]-1, -1, -1):
        if res[j] == 0:
            res[j] = arr[i][1]
            break

print(sum(res))

BOJ 16435 스네이크버드

문제

스네이크버드는 뱀과 새의 모습을 닮은 귀여운 생물체입니다. 

스네이크버드의 주요 먹이는 과일이며 과일 하나를 먹으면 길이가 1만큼 늘어납니다.

과일들은 지상으로부터 일정 높이를 두고 떨어져 있으며 i (1 ≤ i ≤ N) 번째 과일의 높이는 hi입니다. 

스네이크버드는 자신의 길이보다 작거나 같은 높이에 있는 과일들을 먹을 수 있습니다.

스네이크버드의 처음 길이가 L일때 과일들을 먹어 늘릴 수 있는 최대 길이를 구하세요.

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

입력

첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다.

두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다.

출력

첫 번째 줄에 스네이크버드의 최대 길이를 출력합니다.

예제 입력 1

3 10
10 11 13

예제 출력 1

12

스네이크버드의 처음 길이는 10이며 1번 과일을 먹은 후 길이가 11이 됩니다. 

이후 2번 과일을 먹으면 길이가 12가 됩니다. 

더 이상 먹을 수 있는 과일이 없으므로 최대 길이는 12가 됩니다.

예제 입력 2

9 1
9 5 8 1 3 2 7 6 4

예제 출력 2

10

풀이

n, l=map(int, input().split())
h = list(map(int, input().split()))

h.sort()

for i in range(n):
    if l>=h[i]:
        l+=1
print(l)

BOJ 14720 우유 축제

문제

영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.

입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다.

    1. 맨 처음에는 딸기우유를 한 팩 마신다.
    2. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.
    3. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.
    4. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 

영학이는 우유 축제가 열리고 있는 우유거리에 왔다. 

우유 거리에는 우유 가게들이 일렬로 늘어서 있다.

영학이는 우유 거리의 시작부터 끝까지 걸으면서 우유를 사먹고자 한다.

각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다.

각각의 우유 가게 앞에서, 영학이는 우유를 사마시거나, 사마시지 않는다.

우유거리에는 사람이 많기 때문에 한 번 지나친 우유 가게에는 다시 갈 수 없다.

영학이가 마실 수 있는 우유의 최대 개수를 구하여라.

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

입력

첫째 줄에 우유 가게의 수 N이 주어진다. (1 ≤ N ≤ 1000)

둘째 줄에는 우유 가게 정보가 우유 거리의 시작부터 끝까지 순서대로 N개의 정수로 주어진다.

0은 딸기우유만을 파는 가게, 1은 초코우유만을 파는 가게, 2는 바나나우유만을 파는 가게를 뜻하며, 

0, 1, 2 외의 정수는 주어지지 않는다.

출력

영학이가 마실 수 있는 우유의 최대 개수를 출력하시오.

예제 입력 1

7
0 1 2 0 1 2 0

예제 출력 1

7

풀이

n = int(input())       
arr = list(map(int, input().split()))
cnt = 0              

for i in range(n) : 
    if arr[i] == cnt % 3 :	
        cnt += 1

print(cnt)

BOJ 13305 주유소

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 

편의상 일직선을 수평 방향으로 두자. 

제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 

인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 

도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 

기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 

도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 

각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 

가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 

원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 

도로 위에 있는 숫자는 도로의 길이를 표시한 것이다.

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 

만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 

다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 

또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 

4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 

각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 

최소의 비용을 계산하는 프로그램을 작성하시오.

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

입력

표준 입력으로 다음 정보가 주어진다. 

첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 

다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 

다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 

제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 

리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

서브태스크

예제 입력 1

4
2 3 1
5 2 4 1

예제 출력 1

18

예제 입력 2

4
3 3 4
1 1 1 1

예제 출력 2

10

풀이

import sys

input = sys.stdin.readline
k = int(input())
dist = list(map(int, input().split()))
cost = list(map(int, input().split()))
res = 0

c = cost[0]
for i in range(k - 1):
    if c > cost[i]:
        c = cost[i]
    res += c * dist[i]

print(res)

BOJ 4796 캠핑

문제

등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다.

캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다.

강산이는 이제 막 28일 휴가를 시작했다. 

이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까?

강산이는 조금 더 일반화해서 문제를 풀려고 한다. 

캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 

강산이는 이제 막 V일짜리 휴가를 시작했다. 

강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V)

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 

모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다.

출력

각 테스트 케이스에 대해서, 강산이가 캠핑장을 최대 며칠동안 사용할 수 있는지 예제 출력처럼 출력한다.

예제 입력 1 

5 8 20
5 8 17
0 0 0

예제 출력 1

Case 1: 14
Case 2: 11

풀이

import sys

input = sys.stdin.readline
l, p, v = map(int, input().split())
case = 0

while (True):
    if (l==0) and (p==0) and (v==0):
        break
    case += 1
    res = 0
    res = (v//p)*l+min(v%p,l)

    print("Case ",case,": ",res, sep='')

    l,p,v = map(int, input().split())

BOJ 9237 이장님 초대

문제

농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 

묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다.

상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 

이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 

즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.

상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최대한 빨리 초대하려고 한다. 

이장님을 며칠에 초대할 수 있을까?

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

입력

입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 

둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000)

출력

첫째 줄에 며칠에 이장님을 초대할 수 있는지 출력한다.

답이 여러 가지인 경우에는 가장 작은 값을 출력한다. 묘목을 구입한 날이 1일이다.

예제 입력 1

4
2 3 4 3

예제 출력 1

7

예제 입력 2

6
39 38 9 35 39 20

예제 출력 2

42

풀이

n = int(input())
t = list(map(int,input().split()))
t.sort(reverse=True)
res = 0

for i in range(n):
    res = max(res, t[i]+i)

print(res+2)