Hostramus

1. 문제

    5585번 거스름돈 (https://www.acmicpc.net/problem/5585)

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

2. 문제 포인트

• 거스름돈 종류 (500엔, 100엔, 50엔, 10엔, 5엔, 1엔)
• 잔돈 개수의 최소값

3. 접근법

• 큰 금액 동전을 최대한 많이 사용하면 되는 문제
• 1엔짜리까지 있기에 단순하게 계산 가능
    (1엔짜리가 없을 경우 잔돈의 1의 자리가 5나 0으로 끝나지 않으면 계산 불가)

4. 결과 코드

import sys

a = int(sys.stdin.readline())

# 잔돈 금액 계산
chg = 1000 - a

# 동전 단위 리스트 (큰 동전부터 내림차순)
coin = [500, 100, 50, 10, 5, 1]

# 동전 개수
coin_cnt = 0

# coin에 들어있는 동전 단위별로 반복
for n in coin:
    
    # n값으로 나눠지면 계산
    if chg // n > 0:
        # 코인 개수 추가
        coin_cnt += chg // n
        # 현재 단위 제외 후나머지 잔액 계산
        chg -= n * (chg // n)

# 결과값 출력
print(coin_cnt)

# 5585번 거스름돈
# https://www.acmicpc.net/problem/5585

1. 문제

    2810번 컵홀더

    (https://www.acmicpc.net/problem/2810)

십년이면 강산이 변한다.

강산이네 동네에 드디어 극장이 생겼고, 강산이는 극장에 놀러갔다. 매점에서 콜라를 산 뒤, 자리에 앉은 강산이는 큰 혼란에 빠졌다. 양쪽 컵홀더를 이미 옆 사람들이 차지했기 때문에 콜라를 꽂을 컵 홀더가 없었기 때문이다. 영화를 보는 내내 콜라를 손에 들고 있던 강산이는 극장에 다시 왔을 때는 꼭 콜라를 컵 홀더에 놓겠다는 다짐을 한 후 집에 돌아갔다.

극장의 한 줄에는 자리가 N개가 있다. 서로 인접한 좌석 사이에는 컵홀더가 하나씩 있고, 양 끝 좌석에는 컵홀더가 하나씩 더 있다. 또, 이 극장에는 커플석이 있다. 커플석 사이에는 컵홀더가 없다.

극장의 한 줄의 정보가 주어진다. 이때, 이 줄에 사람들이 모두 앉았을 때, 컵홀더에 컵을 꽂을 수 있는 최대 사람의 수를 구하는 프로그램을 작성하시오. 모든 사람은 컵을 한 개만 들고 있고, 자신의 좌석의 양 옆에 있는 컵홀더에만 컵을 꽂을 수 있다.

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

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

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

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

2. 문제 포인트

• 좌석 종류 2가지 (S석(일반석) L석(커플석))
• 컵홀더는 좌석 사이와 양단 끝에 위치
• 최대 컵홀더 사용 가능 인원 수 구하기

3. 접근법

• S는 한글자지만 L은 LL두 글자로 표시됨
• 방법 2가지
  
  • L이 두번 반복되는것을 확인 후 L두번당 한번씩 컵 홀더 위치 시키기
  • LL을 다른 문자 (ex. C)로 치환하여 풀이

4. 결과 코드_1 (LL의 반복을 확인하여 컵홀더 위치시키기)

import sys

a = int(sys.stdin.readline())
b = sys.stdin.readline()

# 시작점 컵홀더 하나 추가
result = "*"

# 각 자리별 컵홀더 자리 *로 표시
## L이 두번 나오는지 검출하는 방법
for n in b:
    # "S"가 나오면 바로 옆에 컵홀더 위치
    if n == "S":
        result += n + "*"

    # 커플석인 L이 나오면 두번 중복되어 나왔는지 확인하여 *추가
    if n == "L":
        if result[-1] == "L":
            result += "L" + "*"
        else:
            result += "L"

# 결과값 출력
## 일반 좌석만 존재하는 경우 컵홀더 숫자가 좌석수(사람수)보다 1개 많아지는 예외 발생
## min으로 컵홀더 사용 개수가 사람수를 넘어가지 않도록 처리
print(min(result.count("*"), a))


# https://www.acmicpc.net/problem/2810

4. 결과 코드_2 (LL 치환을 이용)

import sys

a = int(sys.stdin.readline())
b = sys.stdin.readline().strip()

# LL(커플석)을 하나의 문자로 치환
b = b.replace("LL", "C")

# 컵홀더 수와 사람수를 비교하여 적은 수 출력
print(min(len(b)+1, a))


# https://www.acmicpc.net/problem/2810

1. 문제

    문제번호 문제 타이틀

    (https://www.acmicpc.net/problem/2864)

상근이는 2863번에서 표를 너무 열심히 돌린 나머지 5와 6을 헷갈리기 시작했다.

상근이가 숫자 5를 볼 때, 5로 볼 때도 있지만, 6으로 잘못 볼 수도 있고, 6을 볼 때는, 6으로 볼 때도 있지만, 5로 잘못 볼 수도 있다.

두 수 A와 B가 주어졌을 때, 상근이는 이 두 수를 더하려고 한다. 이때, 상근이가 구할 수 있는 두 수의 가능한 합 중, 최솟값과 최댓값을 구해 출력하는 프로그램을 작성하시오.

2. 문제 포인트

• 5를 6으로, 6을 5로 바꿔 쓸 수 있다
• 최대값과 최솟값을 구하라

3. 접근법

• 최대값 구하기
  = 모든 5를 6으로 바꿔서 합계 출력
• 최솟값 구하기
  = 모든 6을 5로 바꿔서 합계 출력

4. 결과 코드

import sys

a = sys.stdin.readline().strip()


# 입력받은 두 수의 최솟값, 최대값 만들기

## 모든 6을 5로 만들면 최솟값
temp = ""
for num in a:
    if num == "6":
        num = "5"
    temp += num
min_val = list(map(int, temp.split(" ")))


## 모든 5를 6으로 만들면 최대값
temp = ""
for num in a:
    if num == "5":
        num = "6"
    temp += num
max_val = list(map(int, temp.split(" ")))

# 결과 출력
print(f"{sum(min_val)} {sum(max_val)}")


## https://www.acmicpc.net/problem/2864

1. 문제

    25496번 장신구 명장 임스

    (https://www.acmicpc.net/problem/25496)

메이플스토리에는 전문 기술이라는 제작 시스템이 있다. 전문 기술은 특정량의 피로도가 쌓이는 대신 다양한 장비 및 비약을 제작할 수 있는 시스템이다. 장신구 명장인 임스는 어떻게 하면 더 효율적으로 많은 장신구를 제작할 수 있을지 고민에 빠졌다.

임스가 만들 수 있는 장신구는 N개가 있고, 각각의 장신구를 만들면 A만큼의 피로도가 누적된다.

피로도가 200 미만인 경우, 장신구를 제작할 수 있다. 현재 쌓인 피로도가 P일 때, 임스가 제작할 수 있는 장신구의 최대 개수를 구해보자!

2. 문제 포인트

• 만들 수 있는 개수 한정 (N)
• 각 장신구마다 A만큼의 피로도 누적
• 피로도가 200미만이면 제작 가능
  199일때 피로도 100이 누적되는 장신구도 제작 가능
  시작 시점에서 200미만이면 됨
• 최대 개수 구하기

3. 접근법

• 가장 최대 제작 개수가 중요 (피로도에 따른 가중치 없음)
  입력 받은 장신구별 피로도 증가량을 오름차순으로 정렬 후 사용
  

  

4. 결과 코드

import sys

a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))

# 각 아이템별 소모 피로도를 오름차순 정리
b = sorted(b)

cnt = 0

# 전체 횟수 a[1]만큼 반복
## 제한 없이 while True문을 사용할 경우 예외 발생
## ex. 10피로도 2개 아이템 (1, 2) 
for n in range(a[1]):
    # 현재 피로도가 200이상인지 확인하여 True인 경우 for문 종료
    if a[0] >= 200:
        break

    # a[0](현재피로도)에 가장 작은 b값 순차적으로 덧셈
    a[0] = a[0] + b[cnt]
    cnt += 1
    
print(cnt)

# https://www.acmicpc.net/problem/25496

1. 문제
    14655번 욱제는 도박쟁이야!!
    (https://www.acmicpc.net/problem/14655)

욱제는 라스베이거스에서 유명한 베팅꾼이다. 어찌나 게임을 잘 하는지 ‘제2의 홍진호’라는 별명이 붙었을 정도다. 어찌나 게임을 잘 하는지 ‘제2의 홍진호’라는 별명이 붙었을 정도다.

욱제가 주로 하는 게임은 아주 단순하고, 친숙한 게임이다. 바로 동전 뒤집기 게임이다. 이 게임에 쓰이는 동전의 양면에는 절댓값이 같고 부호가 다른 정수가 한 면에 하나씩 쓰여 있다. (단, 동전끼리는 쓰인 수의 절댓값이 다를 수 있다) 한 플레이어 당 두 번의 라운드가 주어진다. 모든 라운드는 같은 동전으로 진행되며, 딜러는 각 라운드마다 N개의 동전을 임의로 섞고 이를 일렬로 배열한다. 이때, 동전의 앞뒤 방향도 바뀔 수 있다. 첫 번째 라운드에서는 동전에 표시된 값들의 합이 최대가 되도록 뒤집어야 하고, 두 번째 라운드에서는 동전에 표시된 값들의 합이 최소가 되도록 뒤집어야 한다. (첫 번째 라운드 동전 값의 합) - (두 번째 라운드 동전 값의 합)이 해당 플레이어가 게임에서 획득한 점수이고, 이 점수가 최대가 되는 플레이어가 바로 게임의 승자가 된다.

욱제는 엄지, 검지, 중지를 이용해서 항상 연속한 3개의 동전을 뒤집는 최고의 동전 뒤집러이다. 욱제는 연속한 3개의 동전을 뒤집지 않으면 이길 수 없다고 생각하기 때문에 실패하는 경우 없이 항상 연속한 3개의 동전만 뒤집는다. 동전 배열의 양 끝에서 벗어나서 양 끝의 동전만 뒤집거나 양 끝의 두 개 동전만 뒤집는 것도 가능하다. 동전을 뒤집는 횟수에 제한은 없다.

(!) 너, 강해 보이는군. 나와 승부를 겨루자! 띠리링띠리링디리ㅣ리리ㅣ링~ 앗! 심술쟁이 해커 임준오(동탄 주민)이 승부를 걸어왔다!

욱제는 이번 게임에서 얼마의 점수를 획득하게 될까? 욱제는 최고의 베팅꾼이기 때문에 항상 게임에서 획득할 수 있는 최고의 점수를 얻는다는 사실은 자명하다.

2. 문제 포인트

• 동전 개수 랜덤
• 3개씩 (양 끝은 1개, 2개씩) 무제한으로 뒤집을 수 있음
• 1라운드 최대 합계, 2라운드 최소 합계로 점수 계산
• 최솟값은 절대값에 '-1'을 곱하면 최솟 합계가 됨

3. 접근법

• 3개씩 (양 끝은 1개, 2개씩) 무제한으로 뒤집을 수 있음
  = 결과적으로 모든 숫자를 양수, 또는 음수로 만들 수 있음
  

  

• 전체 숫자의 절대값을 계산하여 합계를 구하면 해결 가능

4. 결과 코드

import sys

a = sys.stdin.readline()

r1 = list(map(int, sys.stdin.readline().split()))
r2 = list(map(int, sys.stdin.readline().split()))

# 1라운드 최대값 구하기
## 모든 숫자가 양수가 되면 최대값 = 절대값들의 총합
r1 = sum(list(map(abs, r1)))

# 2라운드 최솟값 구하기
## 모든 숫자가 음수가 되면 최대값 = 절대값들의 총합 * -1
r2 = sum(list(map(abs, r2)))

print(r1 + r2)

# https://www.acmicpc.net/problem/14655

1. 문제

19564번 반복

(https://www.acmicpc.net/problem/19564)

muse는 네이버 카페에 글을 올리려고 한다. 하지만 키보드가 고장나서, 어떤 키를 누르든 abcdefghijklmnopqrstuvwxyz가 입력된다!

muse는 글을 올리고 싶지만, 원하는 글을 쓰기 위해서는 아래와 같은 작업을 해야 한다.

1. abcdefghijklmnopqrstuvwxyz를 K번 반복해서 입력한다.
2. 원하는 글자를 마우스로 지워, 최종 글을 완성한다.

muse는 많은 글자를 지우는 일이 귀찮기 때문에, K를 최소화하려 한다. muse가 원하는 글을 입력하려면 abcdefghijklmnopqrstuvwxyz를 몇 번 입력해야 하는지 구해 주자.

2. 문제 포인트

• a-z까지 무조건 입력
  • n번째 글자가 n+1번째 글자보다 앞에(영어 알파벳 순) 있으면 한번입력으로 2개 이상의 글자를 완성 할 수 있음
• a-z 입력 횟수 구하기

3. 접근법

• 입력해야할 글자(input)를 ord()로 아스키 코드로 변환
• n번째 글자와 n+1번째 글자의 아스키 코드를 비교하여 카운트 증가

4. 결과 코드

import sys

a = sys.stdin.readline().strip()

# 처음 한번은 무조건 a-z가 입력되어야 한다
cnt = 1

for i in range(len(a)-1):
    # ascii 코드를 이용해 n번 글자와 n+1번 글자 비교
    if  ord(a[i]) >= ord(a[i+1]):
        cnt += 1

print(cnt)

# https://www.acmicpc.net/problem/19564

1. 문제
    18238번 ZOAC 2 (링크 참고)

    https://www.acmicpc.net/problem/18238

2019년 12월, 두 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.

작년 ZOAC의 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!

규칙은 이러하다.

• 그림과 같은 원판에 문자들이 순서대로 적혀있다. 처음 순간에 화살표는 'A'를 가리키고 있다.
• 원판은 왼쪽 또는 오른쪽으로 돌릴 수 있다. 원판을 한 칸 돌리는 데에는 1의 시간이 소요된다.
• 화살표가 가리키고 있는 문자를 출력할 수 있다. 문자를 출력하는 데에 걸리는 시간은 없다.

시간이 너무 오래 걸리면 지루해할 ZOAC의 참가자들을 위해 성우는 해당 문자열을 앞에서부터 차례대로 최대한 빠르게 출력하려고 한다.

바쁜 성우를 위하여 해당 문자열을 출력하는 데 걸리는 시간의 최솟값을 구해보자.

출처 : 백준 https://www.acmicpc.net/problem/18238

2. 문제 포인트

• 시작은 'A'에서 시작한다
• 원판을 돌려 문자를 찾을때는 왼쪽 오른쪽 모두 가능하다
  = 가까운 쪽으로 돌려야 최솟값을 구할 수 있다.
• 알파벳은 26글자이다
  현재 글자에서 다음 글자로 넘어갈때 중간값인 13초 넘게 걸리지 않는다
  (왼쪽, 오른쪽 모두 회전이 가능하기에 가까운 방향을 이용한다)

3. 접근법

• 각 문자의 좌측으로 이동할때의 소요시간, 우측으로 이동할때의 소요시간을 계산
• 두가지 계산값중 작은값 선택

4. 결과 코드

import sys

a = sys.stdin.readline().strip()
result = 0

# 소문자 입력에 대비해 대문자로 전환
a = a.upper()

# 시작점이 'A'를 추가
a = 'A' + a

for i in range(len(a)-1):
    # chr_1 = 좌측으로 이동할때의 소요시간
    # chr_2 = 우측으로 이동할때의 소요시간
    chr_1 = ord(a[i+1]) - ord(a[i])
    chr_2 = ord(a[i]) - ord(a[i+1])

    # chr_1, chr_2의 계산값이 음수가 나오는 경우 26을 더해 소요 시간 계산
    ## ex. 'AZ'의 경우 chr_2 = 65-90 = -25 음수가 발생
    ##     26을 더해줌으로 1이 되어 좌측으로 돌린 1이란 소요시간 계산 가능
    if chr_1 < 0:
        chr_1 += 26
    if chr_2 < 0:
        chr_2 += 26
    
    # 좌측 우측 이동 소요 시간중 작은값 선택
    result += min(chr_1, chr_2)
print(result)

1. 문제
    욱제는 효도쟁이야!! (링크 참고)

    https://www.acmicpc.net/problem/14487

욱제는 KOI를 망친 기념으로 부모님과 함께 코드게이트 섬으로 여행을 떠났다. 코드게이트 섬에는 오징어로 유명한 준오마을(심술쟁이 해커 임준오 아님), 밥으로 유명한 재훈마을, 영중마을 등 많은 관광지들이 있다. 욱제는 부모님을 모시고 코드게이트 섬을 관광하려고 한다.

코드게이트 섬은 해안가를 따라 원형으로 마을들이 위치해있다. 임의의 A마을에서 임의의 B마을로 가기 위해서는 왼쪽 또는 오른쪽 도로를 통해 해안가를 따라 섬을 돌아야 한다. 섬을 빙빙 도는 원형의 길 외에 다른 길은 존재하지 않는다.

각 마을에서 마을까지의 이동비용이 주어질 때, 욱제가 최소한의 이동비용으로 부모님을 모시고 섬의 모든 마을을 관광하려면 얼마의 이동비용을 준비해야하는지 알려주자.

출처 : 백준 https://www.acmicpc.net/problem/14487

2. 문제 포인트

• 출발 마을은 선택 가능
• 마을에서 이동은 좌우 근접 마을만 이동가능
• 모든 마을 한번씩 방문

3. 접근법

• 최대 비용인 마을에서 시작한다!

• 위의 표를 보면 가장 비싼 구간인 D - C 구간을 피한 4번째 경로가 가장 작은 비용이 든다
• 코드상에서 계산시 가장 큰 비용을 빼고 나머지 비용을 더하면 간단하게 계산된다

4. 결과 코드

import sys

// 마을 개수는 문제 계산과 무관하다
vil_num = sys.stdin.readline()

// 구간별 요금을 리스트로 입력받는다
fee = list(map(int, sys.stdin.readline().split()))

// 구간별 요금 총 합에서 가장 요금이 큰 구간의 요금을 빼면 최소 이동 비용이 나온다
result = sum(fee) - max(fee)

print(result)