i can do ik!

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 2352 반도체 설계

문제

반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 

하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다.

n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 

연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

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

입력

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

다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 

이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력

첫째 줄에 최대 연결 개수를 출력한다.

예제 입력 1

6
4 2 6 3 1 5

예제 출력 1

3

풀이

import sys
import bisect

input = sys.stdin.readline
n = int(input())
port = list(map(int, input().split()))
res = [port[0]]

for i in range(1, n):
    if port[i] > res[-1]:
        res.append(port[i])
    else:
        idx = bisect.bisect_left(res, port[i])
        res[idx] = port[i]

print(len(res))

BOJ 12738 가장 긴 증가하는 부분 수열 3

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

풀이

import sys
import bisect

input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
res = [arr[0]]

for i in range(1, n):
    if arr[i] > res[-1]:
        res.append(arr[i])
    else:
        index = bisect.bisect_left(res, arr[i])
        res[index] = arr[i]

print(len(res))

BOJ 3020 개똥벌레

문제

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 

동굴의 길이는 N미터이고, 높이는 H미터이다. 

(N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 

자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다.

(4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 

이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

예제 입력 1

6 7
1
5
3
3
5
1

예제 출력 1

2 3

예제 입력 2

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

예제 출력 2

7 2

풀이

import sys
import bisect

input = sys.stdin.readline
n, h = map(int, input().split())
top = []
bot = []

for i in range(n):
    if i % 2 == 0:
        bot.append(int(input()))
    else:
        top.append(h-int(input()))
top.sort()
bot.sort()
res = n
cnt = 0

for i in range(h):
    top_idx = bisect.bisect_right(top, i)
    bot_idx = bisect.bisect_right(bot, i)
    cur = top_idx + len(bot) - bot_idx
    if res == cur:
        cnt += 1
    elif res > cur:
        res = cur
        cnt = 1

print(res, cnt)

BOJ 14003 가장 긴 증가하는 부분 수열 5

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4
10 20 30 50

풀이

from bisect import bisect_left

n = int(input())
arr = [0] + list(map(int,input().split()))
d = [0] * (n+1) 
cmp = [-1000000001] 
tmp = 0

for i in range(1, n+1):
    if cmp[-1] < arr[i]: 
        cmp.append(arr[i])
        d[i] = len(cmp) - 1
        tmp = d[i]
    else:
        d[i] = bisect_left(cmp, arr[i]) 
        cmp[d[i]] = arr[i] 
print(tmp) 

res = []

for i in range(n, 0, -1):
    if d[i] == tmp:
        res.append(arr[i])
        tmp -= 1
        
res.reverse()
print(*res)

BOJ 12015 가장 긴 증가하는 부분 수열 2

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

풀이

from bisect import bisect_left
import sys

input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
stack = [0]

for i in arr:
    if stack[-1] < i:
        stack.append(i)
    else:
        stack[bisect_left(stack, i)] = i

print(len(stack)-1)

BOJ 2841 외계인의 기타 연주

문제

상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 

어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 

이제 이 기타를 치려고 한다.

보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 

프렛의 번호도 1번부터 P번까지 나누어져 있다.

멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 

예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 

만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.

예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 

이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 

여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.

이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 

어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000)

다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 

첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 

입력으로 주어진 음의 순서대로 기타를 연주해야 한다.

출력

첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.

예제 입력 1

5 15
2 8
2 10
2 12
2 10
2 5

예제 출력 1

7

예제 입력 2

7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3

예제 출력 2

9

풀이

import sys

input = sys.stdin.readline
n, m = map(int,input().split())
res = 0
stack = [[] for _ in range(7)]

for _ in range(n):
  flag = True
  a, p = map(int, input().split())
  while stack[a] and stack[a][-1] >= p:
    if stack[a][-1] == p:
      flag = False
      break
    stack[a].pop()
    res += 1
  if flag == False:
    continue
  stack[a].append(p)
  res += 1
  
print(res)