졍's 기술 블로그

A와 B

티어 : Gold 5
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 구현, 문자열, 그리디 알고리즘

문제

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

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

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

입력

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

출력

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

예제 입출력

Algorithm

완전 탐색 이용
1. T에서 가장 맨 뒤에 A가 있다면 A 빼기
2. T에서 가장 맨 뒤에 B가 있다면 B 빼고 reverse
3. 1, 2 과정 후 S와 동일한지 확인
4. T의 길이가 0이 되면 BREAK

Code

import sys
input = sys.stdin.readline

S = input().rstrip()
T = input().rstrip()

answer = '0'
while T:
    # T의 가장 맨 뒤에 A가 있다면 A 빼기
    if T[-1] == 'A':
        T = T[:-1]
    else: # T의 가장 맨 뒤에 B가 있다면 B 빼고 reverse
        T = T[:-1]
        T = T[::-1]
    
    # T의 값이 S와 같으면 break
    if T == S:
        answer = '1'
        break
print(answer)

메모리: 30864 KB
시간: 76 ms

주유소

티어 : Silver 4
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 그리디 알고리즘

문제

어떤 나라에 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원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다. 

출력

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

서브태스크

예제 입출력

Algorithm

1. 도로의 길이, 리터 당 가격 각 리스트에 담음
2. 리터 당 가격이 감소하는 시점 찾기
3. 리터 당 가격 i 부터 i+1까지 비용 계산

Code

import sys
input = sys.stdin.readline

# 입력
N = int(input())
length = list(map(int, input().split()))
cost = list(map(int, input().split()))

answer = 0
list_ = [0]
# 감소하는 시점 찾아 각 index를 list에 저장
index = 0
for i in range(1, len(cost)):
    if cost[index] >= cost[i]:
        list_.append(i)
        index = i
    
if list_[-1] != len(cost) - 1:
    list_.append(len(cost) - 1)
    
# i부터 i+1까지 비용 계산
for i in range(len(list_)-1):
    sum_ = sum(length[list_[i]:list_[i+1]])
    answer += cost[list_[i]]*sum_
print(answer)

메모리: 45748 KB
시간: 204 ms

잃어버린 괄호

티어 : Silver 2
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 문자열, 그리디 알고리즘, 파싱

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입출력

Algorithm

1. 숫자는 숫자끼리, 연산자는 연산자끼리 각각 다른 List에 저장
    1.1. 숫자를 저장할 때 자릿수 생각해서 정수로 담기
2. A - B + C의 경우 - 연산자 뒤의 값 모두 계산하기
    2.1. - 연산자가 여러 개 있는 경우 A - B + C - D에서 A - (B+C) - D 로 계산

Code

# 입력
data = input()

operator_ = []
nums = []
temp = []
index = 0
for i in range(len(data)):
    if data[i] in ['+', '-']:
        operator_.append(data[i])
        # 숫자 자릿수에 맞춰서 하나의 숫자로 만들기
        nums.append(0)
        for j in range(len(temp)):
            nums[index] += temp[-1] * (10**j)
            del temp[-1]
        index += 1
    else:
        temp.append(int(data[i]))
# 마지막 숫자 추가
nums.append(0)
for j in range(len(temp)):
    nums[index] += temp[-1] * (10**j)
    del temp[-1]

# - 연산자 나오면 그 다음 - 연산자 전까지 + 모두 계산
i = 0
while True:

    # operator가 비어있으면 while문 돌지 않고 바로 출력
    if not operator_:
        break
    
    # - 연산자가 있으면 -연산자와 -연산자 사이의 값 모두 계산
    if operator_[i] == '-':
        
        index = 0
        flag = False # - 연산자 못찾으면 True
        
        if len(operator_) == 1 or i == len(operator_)-1:
            flag = True
            
        # 다음 - 연산자 찾기
        for j in range(i+2, len(operator_)+1):
            if operator_[j-1] == '-':
                index = j-1
                flag = False
                break
            else:
                flag = True
        
        # 그 뒤에 - 연산자가 없었다면
        if flag == True:
            nums[i+1] = sum(nums[i+1:])
            index = len(nums) - 1
        else: # - 연산자 있으면
            nums[i+1] = sum(nums[i+1:index+1])
        
        # 다음 - 연산자 전까지 모두 계산
        if '+' in  operator_[i+1:index]:
            temp = i + 2
            end = index + 1
            while True:
                nums[i + 2] = 0
                del operator_[i + 1]
                if nums[i + 2] == 0:
                    del nums[i + 2]
                    end -= 1
            
                if i + 2 == end:
                    break

    if i == len(operator_) - 1:
        break
    
    i += 1
    
for i in range(len(operator_)):
    if operator_[i] == '-':
        index = operator_.index('-')
        nums[index] -= nums[index+1]
        del nums[index+1]
print(sum(nums))

메모리: 30864 KB
시간: 76 ms