시간제한: 1초

문제

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다.

예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다.

우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머니가 호랑이를 처음 만난 날에 준 떡의 개수 A, 그리고 그 다음 날에 호랑이에게 준 떡의 개수 B를 계산하는 프로그램을 작성하시오. 이 문제에서는 항상 1 ≤ A ≤ B 이다.

예를 들어 여섯 번째 날에 산을 무사히 넘어온 할머니가 호랑이에게 준 떡이 모두 41개라면, 호랑이를 만난 첫 날에 준 떡의 수는 2개, 둘째 날에 준 떡의 수는 7개이다. 즉 셋째 날에는 9개, 넷째 날에는 16개, 다섯째 날에는 25개, 여섯째 날에는 41개이다. 따라서 A=2, B=7 이 된다. 단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

입력

첫째 줄에는 할머니가 넘어온 날 D (3 ≤ D ≤ 30)와 그 날 호랑이에게 준 떡의 개수 K (10 ≤ K ≤ 100,000)가 하나의 빈칸을 사이에 두고 주어진다.

출력

첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다.

예제 1

# 입력
6 41
# 출력
2
7

예제 2

# 입력
7 218
# 출력
10
21

풀이 과정

문제 해석

초기에 주어진 D, K를 사용하여 A, B를 구하는 문제이다.

사고 흐름

1. 주어야 하는 떡의 개수가 피보나치 수열의 형태로 증가하는 것을 확인했다.
2. 이 규칙을 이용하여 일반식을 만들고 이 식에 D, K 조건을 사용하여 A, B를 구하면 되겠다고 생각했다.
3. 일반식을 구하기 위해 다음과 같이 A, B를 X, Y로 대응하는 표를 그려보았다. (앞으로 편의를 위해 A, B 는 X, Y로 쓰겠다.)
4. 며칠차인지 알 수 있으면 정수 X, Y를 선형결합(aX + bY ; a, b는 정수) 한 식의 값이 정수 K가 되므로 임의의 X, Y 정수 set을 구할 수 있을 것이다.
5. 또한, N일차의 X의 계수는 N-1일차의 Y의 계수와 같으므로 Y의 계수를 구할 때 전날의 계수값도 저장해 두었다가 X의 계수로 활용하면 효율적이겠다라고 생각했다.
6. D일차의 X, Y의 계수를 구했다면 1 ≤ X ≤ Y 조건을 만족하는 X, Y의 값을 구하면 되겠다고 생각했다.
7. Y가 X보다 작을 수는 없으므로 반복문을 Y의 경우의 수 중 최대값에서 점점 감소하도록 구성하는게 좋을 것이다.

코드 작성

#include <stdio.h>

int main(){
    int D = 0, K = 0;
    scanf("%d %d", &D, &K);

    // X, Y의 계수
    int x_coef = 1, y_coef = 1;

    // 피보나치 수열을 이용해 X, Y의 계수 구하기
    for (int i = 2; i < D-1; i++){
        // 전날의 Y계수 임시저장
        int temp = y_coef;

        // 전날의 Y계수에 전전날의 Y계수(전날의 X계수)를 더해 당일의 Y계수 만들기
        y_coef += x_coef;

        // 당일의 X계수를 전날의 Y계수로 설정
        x_coef = temp;
    }

    // 식의 값이 K가 넘지 않게 하는 Y중 최대값
    int y_max = K/y_coef;

    // Y*(Y최대값) 을 K에서 뺀 값을 X의 계수로 나누었을 때 나누어 떨어지지 않으면 Y최대값을 1만큼 감소
    // 나누어 떨어지더라도 X의 값이 0이면 계속 반복
    while ((K - y_max * y_coef) % x_coef != 0 || K - y_max * y_coef == 0){
        y_max--;
    }

    // X(A), Y(B)의 값 출력
    printf("%d\n%d", (K - y_max * y_coef) / x_coef, y_max);

    return 0;
}

총평

조건을 만족하도록 하는 과정에서 시간이 꽤 소요되었다. 브루트포스나 DP 알고리즘에 관련된 문제의 경우 조건을 충분히 고려해주어야겠다고 생각했다.

시간제한: 2초

문제

지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다.

막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.

지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.

1. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
2. 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.

이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다. X가 주어졌을 때, 위의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.

출력

문제의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 출력한다.

예제1

# 입력
23
# 출력
4

예제2

# 입력
32
# 출력
1

예제3

# 입력
64
# 출력
1

예제4

# 입력
48
# 출력
2

풀이 과정

문제 해석

문제에 나온 그대로 구현해서 최종적인 막대의 개수를 구하는 문제이다.

사고 흐름

1. 문제에 구현해야하는 내용이 명확하게 나와있다.
2. 과정을 반복한다 라는 말을 보고 반복문을 사용하면 되겠다고 생각했다.
3. 반복문에서 다룰 변수는 막대의 개수, 제일 작은 막대의 길이, 버린 막대를 제외한 나머지 막대의 길이의 합 이렇게 세 개라고 생각했다.
4. 문제에 나온대로 구현을 하였다.

   코드 작성

X = int(input())

# 초기 막대의 개수
barCnt = 1

# 가장 작은 막대의 길이
smallest = 64

# 버린 막대를 제외한 나머지 막대의 길이의 합
sumOfBarLen = 64

# 막대 길이의 합이 X보다 크지 않을 때까지 반복
while X < sumOfBarLen:
    # 1. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
    smallest //= 2

    # 2. 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 
    # X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
    if sumOfBarLen - smallest >= X:
        sumOfBarLen -= smallest

    # 막대를 버리지 않았다면 자른 막대를 모두 사용함. 즉, 총 막대의 개수가 +1 증가.
    else:
        barCnt += 1

print(barCnt)

위의 코드는 문제에 나와있는 흐름대로 그대로 구현을 한 것이다. 하지만 답을 도출하는 방법을 좀 더 간소화 할 수 있다. X는 자연수이고, 계속 절반으로 자른 막대를 사용하기 때문에 Xcm 길이의 막대기를 구성하는 막대의 길이는 $2^0$, $2^1$ $\dots$ ~ $2^5$, $2^6$가 될 수 밖에 없다. 따라서 64를 2로 나누어 가면서 나누어진 수가 X에 비해 작을 경우 카운트를 +1 하는 방식으로도 구현할 수 있다. 정리하자면 $2^0$, $2^1$ $\dots$ ~ $2^5$, $2^6$ 수를 가장 적게 사용해서 X를 만들 때, 사용한 수를 구하는 것이다. 코드는 다음과 같다.

X = int(input())

# 초기 막대의 개수
barCnt = 0

# 더해나가는 막대의 총 길이
barLen = 0

# 가장 작은 막대의 길이
smallest = 64

while barLen != X:
    if X - barLen >= smallest:
        barLen += smallest
        barCnt += 1
    smallest /= 2
print(barCnt)

총평

문제의 흐름대로 읽어가며 코드로 구현한다면 쉽게 풀리는 문제이다.

시간제한: 2초

문제

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

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

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

입력

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

출력

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

예제1

# 입력
55-50+40
# 출력
-35

예제2

# 입력
10+20+30+40
# 출력
100

예제3

# 입력
00009-00009
# 출력
0

풀이 과정

문제 해석

주어진 식의 값을 최소로 만드는 방법을 찾는 문제이다.

사고 흐름

1. 임의의 괄호를 추가해서 최소값을 만드는 방법의 규칙을 찾아보았다.
2. 식이 -와 +만으로 이루어졌으므로 -연산을 할 때 최대한 많은 항을 같이 묶어 빼주어야 최소값을 만들 수 있을 것 같았다.
3. 식의 앞에서부터 계산을 해 나가다가 -연산이 존재하면 그 뒤에 나오는 -, +연산은 모두 -연산으로 대체 가능하다는 것을 발견했다. (ex. a + b - c + d + e - f $$\rightarrow$$ a + b - (c + d + e) - f)
4. 식의 앞에서부터 차례대로 계산을 하다가 -가 나오면 뒤의 수들을 모두 빼는 코드를 작성했다.

코드 작성

# 식을 -연산자를 기준으로 나누어 배열에 저장
exp = input().split('-')

# -연산을 하지 않는 앞 부분은 결과값에 미리 저장
# -가 나올때까지의 항들은 모두 더해주어야 하므로 sum 사용
# map 함수는 iterable 한 객체를 지정한 파라미터 대로 변환하여 다시 iterable 한 객체로 반환함.
# sum 함수는 list뿐만 아니라 iterable 한 객체를 더해주는 함수이므로 이 경우에 사용 가능하다.
res = sum(map(int, exp[0].split('+')))

# 최초로 나오는 -이후의 항은 모두 결과값에서 빼주기
# 위의 연산과 동일.
for i in exp[1:]:
    res -= sum(map(int, i.split('+')))

print(res)

처음에는 다음과 같은 코드를 작성했다.

exp = str(input())
res = 0

# 이전 정수를 임시로 저장하기 위한 배열
numArr = []

# 전에 -연산자가 나왔을 경우를 다루는 변수 선언
existMinusBefore = False

for i in exp:
    # 정수 처리
    if str.isdigit(i):
        numArr.append(i)
    # 연산자 처리
    else:
        # 이전까지 나온 정수 형변환
        num = int(''.join(numArr))
        numArr = []

        # -연산자가 나왔는지 체크해서 정수의 연산 선택
        if existMinusBefore:
            res -= num
        else:
            res += num

        # 현재 -연산자가 나왔을 경우
        if i == '-': existMinusBefore = True
# 마지막 항 처리
if existMinusBefore:
    res -= int(''.join(numArr))
else:
    res += int(''.join(numArr))

print(res)

코드를 작성하고 보니 -연산자가 한 번만 나오면 뒤의 항들에서는 연산자가 의미가 없어진다는 것을 뒤늦게 깨달았고 연산자를 계속 체크하는 것이 비효율적이라고 느껴졌다. 또한 for문에서 전체 항을 처리하지 못하고 마지막 항을 따로 처리 해주는 것도 불편했다. 그래서 코드를 수정하였다.

총평

그리디 알고리즘과 관련된 문제를 풀 때에는 최대한 문제를 간소화시켜서 구현해보고 필요시 예외처리를 나중에 해주는 방식이 시간을 더 단축할 수 있을 것 같다는 생각이 들었다.

시간제한: 1초

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

예제 입력1

5
3 1 4 3 2

예제 출력1

32

풀이 과정

문제 해석

각 사람들이 현금을 인출하는데 걸리는 시간의 합의 최소값을 구하는 문제.

사고 흐름

1. 어떤 사람의 인출 시간을 구하기 위해서는 그 사람의 인출시간과 앞 사람들의 인출 시간의 합을 구해야 한다.
2. 앞에 있는 사람이 인출하는 시간동안 뒷 사람들의 인출 시간이 모두 늘어나기 때문에 인출 시간이 짧은 사람을 앞에 배치하는 것이 유리하다.(인출 시간의 합을 최소로 만든다.)
3. 매번 저장해놨던 앞사람들의 시간을 각각 더하는 것은 비효율적이다.
4. 반복문을 사용해 이전 사람의 인출 시간을 갱신하며 현재 순회하고 있는 사람의 인출 시간과 더해준 값을 time_sum에 더해나간다면 코드를 간소화 할 수 있을 것이다.

코드 작성

N = int(input())
time_arr = list(map(int, input().split()))

# 인출하는데 걸리는 시간을 오름차순으로 정렬
time_arr.sort()

# 걸리는 시간의 합(결과값)
time_sum = 0

# 이전 사람이 인출하는데 걸리는 시간
time_before = 0

# 각 사람을 순회하며 걸리는 시간과 그 합을 구하기
for i in time_arr:

    # 이전 사람의 인출 시간 + 현재 방문한 사람의 인출 시간
    time_sum += time_before + i

    # 이전 사람의 인출 시간을 현재 사람의 인출 시간으로 갱신
    time_before += i

print(time_sum)

위의 방법은 배열의 각 항목을 순회할 때(각 사람을 순회할 때) 이전사람의 인출 시간과 현재 방문한 사람의 인출 시간만 접근하면 된다. 따라서 $$O(N)$$의 시간복잡도를 가진다.

시간을 더하는 과정에서 배열에 저장되어 있는 시간을 하나씩 다 더하는 방법도 있다. 반복문을 다음과 같이 바꾸어주면 된다.

for x in range(1, N+1):
    time_sum += sum(time_arr[0:x])

하지만 이 경우에는 배열의 각 항목을 순회할 때 sum() 함수를 사용하는데 sum() 함수의 경우 $$O(N)$$의 시간복잡도를 가지므로 전체 for문의 시간 복잡도는 $$O(N^2)$$ 이 된다. $$(1 + 2 +$$ $$\dots$$ $$+ n-1 + n =$$ $$\frac{n(n+1)}{2}$$ $$)$$ 따라서 이전 방법보다 가독성은 좋지만 성능이 떨어진다.

총평

인출 시간의 최솟값을 어떻게 구해야할지 아이디어만 있다면 쉬운 문제라고 생각한다.

시간제한: 2초

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

예제 입력1

4 6
a t c i s w

예제 출력1

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

풀이 과정

사고 흐름

1. 사전식으로 출력을 해야함. --> 처음에 주어진 문자들을 정렬해야겠다.
2. 정렬된 문자들을 가지고 암호를 어떻게 만들어야 할까?
3. 필수로 들어가는 모음과 자음을 고정하고 나머지를 채울까? --> 방법이 생각 안남/ 방법이 존재하더라도 비효율적일 것 같음.
4. 문자 L개로 만들 수 있는 문자열의 모든 경우를 탐색하면서 조건에 맞는 문자열만 결과로 출력하자. (모든 경우 탐색시에도 최대 $${15}C{7} = 6435$$ 개의 문자열만 생성하기 때문에 시간제한을 넘지 않을 것이라고 생각함.)
5. 모든 경우의 문자열을 만드는 방법 / 조건에 맞는 문자열 분리 방법 을 생각해보자.
6. 모든 경우의 문자열을 만드는 방법의 경우 파이썬 itertools에 내장되어 있는 combinations(조합) 모듈을 사용하면 될 것이라고 생각함.
7. 조건에 맞는 문자열 분리 방법의 경우 모음set을 만들어 생성된 문자열과의 집합 연산으로 모음과 자음의 개수를 알 수 있을 것이라고 생각함.

코드 작성

from itertools import combinations

L, C = map(int, input().split())
input_arr = list(map(str, input().split()))

# 입력받은 문자 사전식 정렬
input_arr.sort()

# 모음 set 정의
vowel_set = {'a', 'e', 'i', 'o', 'u'}

res_arr = []

# combinations 는 tuple을 반환 하는 iterator을 반환
for pw_case in combinations(input_arr, L):
    # 최소 한 개의 모음, 최소 두 개의 자음 조건을 만족하는 pw_case만 res_arr에 추가
    if len(set(pw_case) & vowel_set) > 0 and len(set(pw_case) - vowel_set) > 1 :
        res_arr.append(pw_case)

# pw는 tuple형태로, 출력 형식에 맞게 가공
for pw in res_arr:
    for word in pw:
        print(word, end='')
    print("")

총평

경우를 다 구하여 조건에 맞게 걸러낸다는 생각, 그리고 그 방법을 떠올리는 것이 관건이었다고 생각한다.