i can do ik!

BOJ 2828 사과 담기 게임

문제

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다.

스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. 

(M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 

하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.

스크린의 위에서 사과 여러 개가 떨어진다. 

각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 

한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.

바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 

상근이는 사과를 모두 담으려고 한다. 

이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다.

(1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.

출력

모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.

예제 입력 1 

5 1
3
1
5
3

예제 출력 1

6

예제 입력 2

5 2
3
1
5
3

예제 출력 2

4

풀이

n, m = map(int, input().split())
j = int(input())
apple = []
 
for _ in range(j):
    apple.append(int(input()))
 
res = 0
end = m     
start = 1   
 
for i in range(j):
    if(end >= apple[i] and start <= apple[i]):
        continue
    elif (end < apple[i]):
        res += apple[i] - end
        end = apple[i]
        start = apple[i] - (m - 1)
    elif (start > apple[i]):
        res += start - apple[i]
        start = apple[i]
        end = apple[i] + (m - 1)
 
print(res)

BOJ 19941 햄버거 분배

문제

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 

사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다.

위의 상태에서 K = 1인 경우를 생각해보자. 

이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 

10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 

이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

2번 위치에 있는 사람: 1번 위치에 있는 햄버거
4번 위치에 있는 사람: 5번 위치에 있는 햄버거
6번 위치에 있는 사람: 7번 위치에 있는 햄버거
9번 위치에 있는 사람: 8번 위치에 있는 햄버거
10번 위치에 있는 사람: 11번 위치에 있는 햄버거
12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

K = 2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

2번 위치에 있는 사람: 1번 위치에 있는 햄버거
4번 위치에 있는 사람: 3번 위치에 있는 햄버거
6번 위치에 있는 사람: 5번 위치에 있는 햄버거
9번 위치에 있는 사람: 7번 위치에 있는 햄버거
10번 위치에 있는 사람: 8번 위치에 있는 햄버거
12번 위치에 있는 사람: 11번 위치에 있는 햄버거

식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때, 

햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

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

입력

첫 줄에 두 정수 N과 K가 있다.

그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 N인 문자열로 주어진다.

출력

첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.

제한

 1 <= N <= 20,000
 1 <= K <= 10

예제 입력 1

20 1
HHPHPPHHPPHPPPHPHPHP

예제 출력 1

8

예제 입력 2

20 2
HHHHHPPPPPHPHPHPHHHP

예제 출력 2

7

풀이

import sys

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

for i in range(n):
    if arr[i] == 'P':
        for j in range(i - k, i + k + 1):
            if -1 < j < n:
                if arr[j] == 'H':
                    arr[j] = '-'
                    res += 1
                    break

print(res)

BOJ 2012 등수 매기기

문제

2007년 KOI에 N명의 학생들이 참가하였다. 

경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.

KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다.

1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 

어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다.

당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.

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

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 

둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다.

예상 등수는 500,000 이하의 자연수이다.

출력

첫째 줄에 불만도의 합을 최소로 할 때, 그 불만도를 출력한다.

예제 입력 1 

5
1
5
3
1
2

예제 출력 1

3

풀이

import sys

input = sys.stdin.readline
n = int(input())
s = []
for i in range(n):
    s.append(int(input()))

s.sort()
res = 0
for i in range(1, n + 1):
    res += abs(i - s[i - 1])
print(res)

BOJ 15904 UCPC는 무엇의 약자일까?

문제

UCPC는 '전국 대학생 프로그래밍 대회 동아리 연합 여름 대회'의 줄임말로 알려져있다. 

하지만 이 줄임말이 정확히 어떻게 구성되었는지는 아무도 모른다. 

UCPC 2018을 준비하던 ntopia는 여러 사람들에게 UCPC가 정확히 무엇의 줄임말인지 물어보았지만,

아무도 정확한 답을 제시해주지 못했다. ntopia가 들은 몇 가지 답을 아래에 적어보았다.

Union of Computer Programming Contest club contest
Union of Computer Programming contest Club contest
Union of Computer Programming contest club Contest
Union of Collegiate Programming Contest club contest
Union of Collegiate Programming contest Club contest
Union of Collegiate Programming contest club Contest
University Computer Programming Contest
University Computer Programming Club contest
University Computer Programming club Contest
University Collegiate Programming Contest
University CPC
...

ntopia는 이렇게 다양한 답을 듣고는 UCPC가 무엇의 약자인지는 아무도 모른다고 결론내렸다. 

적당히 슥삭해서 UCPC를 남길 수 있으면 모두 UCPC의 약자인 것이다!

문자열이 주어지면 이 문자열을 적절히 축약해서 "UCPC"로 만들 수 있는지 확인하는 프로그램을 만들어보자.

축약이라는 것은 문자열에서 임의의 문자들을 제거하는 행동을 뜻한다. 

예를 들면, "apple"에서 a와 e를 지워 "ppl"로 만들 수 있고, 

"University Computer Programming Contest"에서 공백과 소문자를 모두 지워 "UCPC"로 만들 수 있다.

문자열을 비교할 때는 대소문자를 구분해 정확히 비교한다. 

예를 들어 "UCPC"와 "UCpC"는 다른 문자열이다. 

따라서 "University Computer programming Contest"를 "UCPC"로 축약할 수 있는 방법은 없다.

그나저나 UCPC는 정말 무엇의 약자였을까? 정확히 아시는 분은 제보 부탁드립니다.

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

입력

첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 

문자열의 길이는 최대 1,000자이다. 

문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 경우도 없다.

출력

첫 번째 줄에 입력으로 주어진 문자열을 적절히 축약해 "UCPC"로 만들 수 있으면 "I love UCPC"를 출력하고, 

만들 수 없으면 "I hate UCPC"를 출력한다.

예제 입력 1

Union of Computer Programming Contest club contest

예제 출력 1

I love UCPC

예제 입력 2

University Computer Programming

예제 출력 2

I hate UCPC

풀이

n = input()
ucpc = ['U', 'C', 'P', 'C']
res = ""
cnt = 0

for i in n :
    if res == "UCPC" : break 
    elif i.isupper() and i == ucpc[cnt] : 
        res += i 
        cnt += 1

if res == "UCPC" : 
    print("I love UCPC")
else : 
    print("I hate UCPC")

BOJ 12904 A와 B

문제

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 

대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다.

두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다.

문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

1. 문자열의 뒤에 A를 추가한다.
2. 문자열을 뒤집고 뒤에 B를 추가한다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. 

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

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

예제 입력 1

B
ABBA

예제 출력 1

1

예제 입력 2

AB
ABB

예제 출력 2

0

풀이

import sys

input = sys.stdin.readline
s = list(input().rstrip())
t = list(input().rstrip())

while len(s) != len(t):
    if t[-1] == "A":   
        t.pop()
    else:              
        t.pop()
        t.reverse()

if s == t:
    print(1)
else:
    print(0)

BOJ 1946 신입 사원

문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 

인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 

최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 

다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 

즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 

각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다.

두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력 

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

예제 입력 1

2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1

예제 출력 1

4
3

풀이

import sys

input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    l = [0] * (n + 1)
    for o in range(n):
        x, y = map(int, input().split())
        l[x]=y
    min_=100_001
    cnt = 0
    for i in range(1,len(l)):
        if  l[i] < min_: 
            min_ = l[i]
            cnt += 1
    print(cnt)

BOJ 2810 컵홀더

문제

십년이면 강산이 변한다.

강산이네 동네에 드디어 극장이 생겼고, 강산이는 극장에 놀러갔다. 

매점에서 콜라를 산 뒤, 자리에 앉은 강산이는 큰 혼란에 빠졌다.

양쪽 컵홀더를 이미 옆 사람들이 차지했기 때문에 콜라를 꽂을 컵 홀더가 없었기 때문이다.

영화를 보는 내내 콜라를 손에 들고 있던 강산이는 극장에 다시 왔을 때는 꼭 콜라를 컵 홀더에 놓겠다는 다짐을 한 후 집에 돌아갔다.

극장의 한 줄에는 자리가 N개가 있다. 

서로 인접한 좌석 사이에는 컵홀더가 하나씩 있고, 양 끝 좌석에는 컵홀더가 하나씩 더 있다. 

또, 이 극장에는 커플석이 있다. 커플석 사이에는 컵홀더가 없다.

극장의 한 줄의 정보가 주어진다. 

이때, 이 줄에 사람들이 모두 앉았을 때, 컵홀더에 컵을 꽂을 수 있는 최대 사람의 수를 구하는 프로그램을 작성하시오. 

모든 사람은 컵을 한 개만 들고 있고, 자신의 좌석의 양 옆에 있는 컵홀더에만 컵을 꽂을 수 있다.

S는 일반 좌석, L은 커플석을 의미하며, L은 항상 두개씩 쌍으로 주어진다.

어떤 좌석의 배치가 SLLLLSSLL일때, 컵홀더를 *로 표시하면 아래와 같다.

*S*LL*LL*S*S*LL*

위의 예에서 적어도 두 명은 컵홀더를 사용할 수 없다.

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

입력

첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다.

출력

컵을 컵홀더에 놓을 수 있는 최대 사람의 수를 출력한다.

예제 입력 1

3
SSS

예제 출력 1

3

예제 입력 2

4
SLLS

예제 출력 2

4

예제 입력 3

9
SLLLLSSLL

예제 출력 3

7

풀이

n = int(input())
data = input()
cnt = 0

for i in range(len(data)):
  if data[i] == 'L':  
    cnt += 1
 
if cnt == 0: 
  print(n)
else:
  print(n-(cnt//2-1))

BOJ 15903 카드 합체 놀이

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 

오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 

카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. 

m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 

이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 

아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 

그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다.

만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

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

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입력 1

3 1
3 2 6

예제 출력 1

16

예제 입력 2

4 2
4 2 3 1

예제 출력 2

19

풀이

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
card  = list(map(int, input().split()))

for _ in range(m):
    card = sorted(card)
    cover = card[0] + card[1]
    card[0] = cover
    card[1] = cover

print(sum(card))