i can do ik!

BOJ 1059 좋은 구간

문제

정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다.

1. A와 B는 양의 정수이고, A < B를 만족한다.
2. A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.

집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자.

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

입력

첫째 줄에 집합 S의 크기 L이 주어진다. 

둘째 줄에는 집합에 포함된 정수가 주어진다. 

셋째 줄에는 n이 주어진다.

출력

첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다.

제한

* 1 ≤ L ≤ 50
* 집합 S에는 중복되는 정수가 없다.
* 집합 S에 포함된 모든 정수는 1보다 크거나 같고, 1,000보다 작거나 같다.
* 1 ≤ n ≤ (집합 S에서 가장 큰 정수)

예제 입력 1

4
1 7 14 10
2

예제 출력 1

4

예제 입력 2

5
4 8 13 24 30
10

예제 출력 2

5

예제 입력 3

5
10 20 30 40 50
30

예제 출력 3

0

예제 입력 4

8
3 7 12 18 25 100 33 1000
59

예제 출력 4

1065

풀이

l = int(input())
arr = list(map(int, input().split()))
n = int(input())
arr.insert(0, 0)  
arr.sort()

if n in arr: 
    print(0)
else:
    for i in range(l):
        if arr[i] < n < arr[i + 1]:  
            res = (n - arr[i]) * (arr[i + 1] - n) - 1
            print(res)
            break

BOJ 18310 안테나

문제

일직선 상의 마을에 여러 채의 집이 위치해 있다. 

이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 

효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다.

이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다.

집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오.

예를 들어 N=4이고, 각 위치가 1, 5, 7, 9일 때를 가정하자.

이 경우 5의 위치에 설치했을 때, 안테나로부터 모든 집까지의 거리의 총 합이 (4+0+2+4)=10으로, 최소가 된다.

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

입력

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

둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다.

출력

첫째 줄에 안테나를 설치할 위치의 값을 출력한다. 

단, 안테나를 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우 가장 작은 값을 출력한다.

예제 입력 1

4
5 1 7 9

예제 출력 1

5

풀이

import sys

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

arr.sort()
print(arr[(n-1)//2])

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

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)