기초 알고리즘 스터디 1주차 모의 테스트 해설

1. [BOJ 4435] 중간계 전쟁

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

4435번: 중간계 전쟁

문제에서 요구한 대로 아래 내용에 맞게 점수를 곱해 더해주면 되는 문제입니다.

 

간달프

• 호빗 - 1
• 인간 - 2
• 엘프 - 3
• 드워프 - 3
• 독수리 - 4
• 마법사 - 10

사우론

• 오크 - 1
• 인간 - 2
• 워그(늑대) - 2
• 고블린 - 2
• 우럭하이 - 3
• 트롤 - 5
• 마법사 - 10

t = int(input())
for i in range(t):
    a1, a2, a3, a4, a5, a6 = map(int, input().split())
    b1, b2, b3, b4, b5, b6, b7 = map(int, input().split())

    A = a1 * 1 + a2 * 2 + a3 * 3 + a4 * 3 + a5 * 4 + a6 * 10
    B = b1 * 1 + b2 * 2 + b3 * 2 + b4 * 2 + b5 * 3 + b6 * 5 + b7 * 10

    if A > B: print('Battle {}: Good triumphs over Evil'.format(i+1))
    elif A < B: print('Battle {}: Evil eradicates all trace of Good'.format(i+1))
    else: print('Battle {}: No victor on this battle field'.format(i+1))

 

 

 

2. [BOJ 1357] 뒤집힌 덧셈

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

1357번: 뒤집힌 덧셈

 

문자열을 뒤집는 방법인 [::-1]을 사용하는 간단한 문제입니다.

C++ 같은 경우엔 새로운 배열을 만들어서 for문을 사용하여 거꾸로 값을 채울 수도 있습니다.

1. 먼저 Rev(X) + Rev(Y)는 X[::-1] + Y[::-1]이고, 둘이 더해야하니까 int형으로 바꾸어줍니다.

→ int(X[::-1]) + int(Y[::-1])

2. 이제 Rev(Rev(X) + Rev(Y))를 해야하니까 윗 줄에서 구한 값은 정수형이니 다시 문자열로 바꿔주고 뒤집어줍니다.

→ str(int(X[::-1]) + int(Y[::-1]))[::-1]

3. 마지막으로 예시를 보면 5 + 5인 경우 01이 아닌 1을 출력하고 있으니 int형으로 설정을 해줍니다.

→ int(str(int(X[::-1]) + int(Y[::-1]))[::-1])

 

x, y = input().split()
print(int(str(int(x[::-1]) + int(y[::-1]))[::-1]))

 

 

3. [BOJ 2869] 달팽이는 올라가고 싶다

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

2869번: 달팽이는 올라가고 싶다

A만큼 더하고, B만큼 빼는 것을 계속 반복하였으면 시간 초과가 나왔을 것이라고 생각합니다.

왜 이런 방법으로는 시간 초과가 나오냐면 이 문제의 시간 제한이 0.15초이기 때문인데, 대략 1억번의 연산을 하면 1초가 걸린다고 생각하시면 됩니다.

그래서 만약 A = 2, B = 1, V = 1,000,000,000이 입력값으로 들어온다면 A만큼 더하고, B만큼 빼는 것의 연산이 두 번인데, 높이가 1씩 올라가니 1,000,000,000 = 10억번의 연산을 해야 올라갈 수 있어서 약 10초의 시간이 걸리게 됩니다.

 

그래서 위의 연산을 빠르게 하는 방법이 필요한데, 문제 내용을 곰곰히 생각해보면 결국 달팽이가 하루종일 이동하는 높이는 (A - B)인 것이니까 여기서 두 번의 연산이 한 번으로 줄어듭니다.

거기다가 달팽이는 마지막에 도착하기 직전에 낮에 A만큼 높이를 올라가서 도착하지, 밤에 B만큼 미끄러진뒤에 도착할리가 없다는 사실을 이용하여 (V - A)를 (A - B)로 나눈 몫을 구해주면 됩니다. 만약 나눴을 때 나머지가 존재하면 하루 더 움직여야하니 1을 더해주면 됩니다.

 

a, b, v = map(int, input().split())
v -= a
if v % (a - b) == 0: print(v // (a - b) + 1)
else: print(v // (a - b) + 2)

여기서 모든 출력 값에 1을 더 더해주는 것은 낮에 움직여서 도착하는 것이기 때문에 해당 부분을 주의해서 코드를 작성하면 됩니다.

 

 

 

4. [BOJ 3135] 라디오

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

3135번: 라디오

 

• 첫 번째 버튼은 주파수를 1MHz 증가시킨다.
• 두 번째 버튼은 주파수를 1MHz 감소시킨다.
• 나머지 N개의 버튼은 즐겨찾기 기능으로, 미리 지정된 주파수로 이동한다.

주파수 A에서 B로 갈 때 눌러야하는 버튼 수의 최솟값을 구하라고 합니다.

 

먼저 주파수의 값중 가장 큰 값이 1,000이고, 즐겨찾기를 할 수 있는 주파수도 최대 5이므로 모든 경우의 수를 확인하여 문제를 풀 수 있습니다.

여기서 모든 경우의 수란 A부터 시작해서 주파수 증가/감소 버튼을 계속 누르기, A부터 시작하여 즐겨찾기 주파수를 하나 눌러 주파수 증가/감소 버튼을 계속 누르는 경우 입니다.

이때 주파수 증가/감소 버튼을 섞어가면서 누르는 것이 아닌 한 버튼만 쭉 누르는 것이 각 주파수에 도달할 수 있는 최소값입니다.

그리고 어떤 주파수에 도달할 수 있는 경우의 수가 A부터 시작, 즐겨찾기1에서 시작, 즐겨찾기2에서 시작, ... 이렇게 있는데, 이중에서 가장 적게 버튼을 누른 횟수의 값을 선택해주면 됩니다.

 

이건 코드를 보면서 해설을 하겠습니다.

 

먼저 a와 b의 입력값을 받아줍니다.

a, b = map(int, input().split())

 

여기서 제일 처음으로 주파수 A에서 시작하니 2개의 for문을 사용해서 하나는 계속 1MHz씩 증가시키고, 하나는 계속 1MHz씩 감소시킵니다.

a, b = map(int, input().split())
MAX = 1000
count = [0] * (MAX + 1)

for i in range(1, MAX):
    if a + i > MAX: break
    count[a + i] = i
for i in range(1, MAX):
    if a - i <= 0: break
    count[a - i] = i

여기서 MAX의 값은 최대 주파수가 될 수 있는 것이 1000이라고 했으니 MAX = 1000으로 잡아주고, count의 값은 어떤 주파수 x에 왔을 때 버튼을 누르는 최소 횟수인데, 아직 시작을 안했으니 전부 0으로 초기화를 합니다.

 

첫 번째 for문은 주파수 A에서 시작하여 1MHz씩 주파수를 증가하는 버튼을 누르는 경우입니다.

이때 i를 버튼을 누른 횟수로 하여 a + i가 1000을 넘어가면 안되니까 break문을 해주고, 주파수가 1000이하인 경우에는 a에서 a + i로 가려면 i번 버튼을 눌러야하니 count[a + i] = i로 설정합니다.

 

두 번째 for문도 비슷하게 주파수 A에서 시작하여 1MHz씩 주파수를 감소하는 버튼을 누르는 경우입니다.

이때 i를 버튼을 누른 횟수로 하여 주파수인 a - i가 0이하면 안되니까 break문을 설정하고, 주파수가 0이상인 경우에는 a에서 a - i로 가려면 i번 버튼을 눌러야하니 count[a - i] = i로 설정합니다.

 

이제 즐겨찾기도 이와 비슷한 방법으로 해주면 됩니다.

a, b = map(int, input().split())
MAX = 1000
count = [0] * (MAX + 1)

for i in range(1, MAX):
    if a + i > MAX: break
    count[a + i] = i
for i in range(1, MAX):
    if a - i <= 0: break
    count[a - i] = i

n = int(input())
for i in range(n):
    k = int(input())
    count[k] = min(count[k], 1)

    for j in range(1, MAX):
        if k + j > MAX: break
        count[k + j] = min(count[k + j], j + 1)
    for j in range(1, MAX):
        if k - j <= 0: break
        count[k - j] = min(count[k - j], j + 1)

print(count[b])

먼저 즐겨찾기 버튼을 한 번 눌러야하는데, 이때 즐겨찾기의 값이 A인 경우도 있으니까 min()함수를 적용해줍니다.

그리고 위에서 구한 for문과 마찬가지의 방법으로 count의 값을 업데이트해주면 됩니다.

마지막으로 count[b]를 출력해주면 A에서 B로 가는데 버튼을 눌러야하는 최소 횟수를 출력할 수 있게 됩니다.

 

 

5. [BOJ 9996] 한국이 그리울 땐 서버에 접속하지

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

9996번: 한국이 그리울 땐 서버에 접속하지

 

마지막은 문자열 문제입니다.

a*b일 경우 맨 첫번째 글자와 맨 마지막 글자가 a와 b이고, *은 공백이 와도 상관이 없다고 하였으니 a*b가 나타낼 수 있는 길이는 최소 2라는 뜻입니다.

 

바로 풀이부터 말하자면 우리는 문자열 첫 번째 글자에서 시작하여 *이 나올 때까지의 인덱스와 문자열 맨 마지막 문자에서 시작하여 *이 나올 때까지의 인덱스를 구할 수 있고, 이것을 다음 문자열들에 적용하는 것입니다.

그래서 첫 번째 글자에서 시작하는 것은 문자열의 왼쪽에서 시작하는 것과 같으니 변수를 left인 l로 설정하고, 마지막 글자에서 시작하는 것은 문자열의 오른쪽에서 시작하는 것과 같으니 변수를 right인 r로 설정하여 총 2개의 for문으로 *이 나오기 직전까지의 인덱스 번호를 확인합니다.

그래서 아래의 코드가 해당 내용을 처리하는 코드가 되겠습니다.

n = int(input())

s = input()
l, r = 0, 0
for i in range(len(s)):
    if s[i] == "*": break
    l += 1
for i in range(len(s)-1, -1, -1):
    if s[i] == "*": break
    r += 1

 

여기서 이제 파일 이름이 주어지는데, 여기서 많이 실수할 수 있는 부분은 파일 이름의 길이가 패턴에서 *을 뺀 길이보다 크거나 같아야 하는 것입니다.

반례로 코드를 짰을 때 a*a가 주어지고 파일 이름이 a일 경우엔 답이 아니게 됩니다. 왜냐하면 *은 공백이 될 수 있지만 다른 문자열은 공백이 될 수 없기 때문에 패턴에 맞는 파일 이름이 되려면 최소 aa가 되어야 합니다.

 

이후엔 인덱스를 0부터 l까지 패턴과 파일 이름이 같은지 확인해보고, 인덱스를 r부터 (문자열의 길이)-1까지 같은지 확인해봐야 하는데, 여기도 구하기 조금 까다롭습니다.

 

n = int(input())

s = input()
l, r = 0, 0
for i in range(len(s)):
    if s[i] == "*": break
    l += 1
for i in range(len(s)-1, -1, -1):
    if s[i] == "*": break
    r += 1

for i in range(n):
    k = input()

    flag = True
    for j in range(min(len(k), l)):
        if k[j] != s[j]:
            flag = False
    for j in range(min(r, len(k))):
        if k[-j-1] != s[-j-1]:
            flag = False
    
    if len(s) - 1 > len(k):
        flag = False

    if flag: print("DA")
    else:print("NE")

이중 for문을 보면 min(len(k), l)과 min(r, len(k))가 있는데, k의 문자열의 길이가 l, r보다 작을 수 있기 때문에 min()함수를 통해 만약 len(k)의 값이 l, r보다 작으면 오류가 나오지 않고 통과할 수 있게하고, 이중 for문 다음에서 문자열의 길이가 작을 때 flag = False로 설정할 수 있게끔 만들어두었습니다.

 

이후 flag의 값이 True이면 DA를 출력하고 flag의 값이 False이면 NE를 출력하시면 됩니다.