[CLASS 2]백준 2869번, 15829번, 1259번, 2839번, 11050번

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

 

문제가 엄청 쉬워 보이는데 정답률이 26퍼다? 이건 무조건 함정이 있거나 많은 사람이 간과하는 무엇이 있다는 이야기이다. 그리고 문제를 처음 보고 든 생각으로 그냥 코드를 짰다면 이런 코드가 나왔을 것이다.

a,b,v = map(int,input().split())
day = 0
while True:
	day += 1
	v -= a
    if v <= 0:
    	break
    v += b

print(day)

 

가장 직관적이고 간단한 코드인데, 이 코드의 문제는 숫자가 커지면 계산하는데 시간이 꽤 걸린다는 것이다. 실제로 이런 식의 코드를 짠 뒤 내 15년형 맥프레로 100 99 1000000000 을 입력해 보았는데, 기다려 보아도 day 가 출력되지 않았다.

 

문제를 자세히 보면 시간 제한에 0.15초 라고 써있는 것이 보인다. 시간을 고려하면 이런 코드를 짤 수 있다.

 

내 코드:

import math
a,b,v = map(int,input().split())
print(math.ceil((v - a) / (a - b)) + 1)

이 문제는 낮에 도착점에 도착하게 된다면, 밤에 뒤로 가지 않고 그냥 끝나게 된다는 것에 있다. 즉 v - a <= x < v 라는 지점에서 낮이 된다면, 그 날 등반은 종료되고 뒤로 가지 않는다.

 

다시 말하면, 이 날까지는 하루에 a - b 만큼 간다고 생각해도 무방한 것이다.

 

결국 v - a를 a - b 로 나눈 몫 (나머지가 있다면 올림)은 도착하기 하루 전날이 될 것이고, 그 다음날 낮에 도착점을 찍게 된다.

 

15829번 : Hashing

 

문제는 간단히 문자열을 수열로 바꿔서 특정 규칙을 이용해 더한 후 모듈러 연산(나머지 연산) 을 통해 해시 함수를 구현하라는 것이다. 설명은 길고 수식도 막 나오는데 별로 어렵지 않다.

 

내 코드:

n = int(input())
string = input()
answer = 0
for i in range(n):
    answer += ((ord(string[i]) - 96) * 31**i)
print(answer % 1234567891)

 

함수를 만들어서 매개변수를 넘기고 리턴값을 주는 방식이 문제의 취지에 더 맞을 것 같긴 하지만, 로직은 같다.

 

문자열을 받아서 ord함수를 통해 각각의 문자를 아스키 코드의숫자로 바꿔준다. -96이 나온 이유는, 아스키 코드의 97번부터 소문자 a 가 시작되기 때문에, a를 1로 매칭시키기 위해 사용했다.

 

이런 식으로 다 더한 후 마지막 M 값인 1234567891로 나눈 나머지를 출력해 준다.

 

1259번 : 펠린드롬수

 

앞뒤가 같은 숫자를 판별하는 문제이다. 어렵지 않다.

 

내 코드:

arr = []
while True:
    arr.append(input())
    if arr[-1] == '0':
        arr.pop()
        break

for obj in arr:
    if len(obj) == 1:
        print('yes')
    for i in range(len(obj) // 2):
        if obj[i] == obj[-1*(i+1)]:
            if i == len(obj) // 2 - 1:
                print('yes')
        else:
            print('no')
            break

배열을 만들어 input을 받아 넣되, 마지막 요소가 '0' 이면 받는 행위를 그만둔다.

 

이후 해당 배열에서 하나씩 뽑아서 펠린드롬수인지를 판별한다.

 

일단 한 자리 숫자라면 펠린드롬수이므로 yes 출력.

 

두 자리수 이상이라면 해당 수를 2로 나눈 몫에 해당하는 횟수 만큼, 양쪽 끝 문자부터 차례로 비교한다.

 

음수를 통해 거꾸로 인덱싱할수 있는 파이썬이 이럴때 참 좋은 것 같다.

 

만약 마지막 문자까지 비교하고 같다면, yes를 출력한다.

 

도중 하나라도 다른 문자열 쌍이 있다면 no 를 출력하고 다음 obj에 대해 검사하면 된다.

 

jmkk27님의 코드:

import sys
input=sys.stdin.readline
while 1:
  s=input().rstrip()
  if s=='0': break
  print('yes' if s==s[::-1] else 'no')

 

그냥 슬라이싱에 음수 인덱스를 사용하면 문자열을 거꾸로 뒤집어 버리는것도 가능하다... 킹갓 파이썬..

 

2839번 : 설탕 배달

 

뭔가 어디서 본 것 같은... 그런 문제이다. 3KG 봉지와 5KG 봉지를 잘 조합하여 총 무게를 가장 적은 봉지의 수로 옮기는 문제이다.

 

내 코드:

def find(N):
    for five in range(N // 5,-1,-1):
        for three in range(N // 3 + 1):
            sum = three*3 + five*5
            if(sum == N):
                return three+five
            elif(sum > N):
                break
    return -1

print(find(int(input())))

 

일단 이 생각을 해야 한다. 5KG 봉지를 가장 많이 사용하는 경우부터 시작하여 이를 줄여가는 방법을 사용해야 가장 빨리 답을 얻을 수 있다. 가장 간단한 그리디 알고리즘이라고 할 수 있겠다.

 

그래서 이러한 코드를 작성한 것이다. five는 5KG 봉지의 수, three는 3KG 봉지의 수 이다.

 

만약 sum이 원하는 총 무게(N)와 같다면 즉시 이 조합을 리턴하고, sum 이 더 크다면 5KG 봉지를 하나 줄여 본다. 만약 5KG 봉지를 충분히 줄였는데도(0개 까지) sum과 N 이 일치하지 않는다면 답이 없는 것이다.

 

cleske님의 코드:

n = int(input())

a = n//5
b = n%5
c = 0

while a>=0:
    if b%3 == 0:
        c = b//3
        
        break
    a -= 1
    b += 5
        
if b%3 == 0:
    print(a+c)
else:
    print(-1)

 

사실 내가 작성한 코드는 이중 for 문이 있기 때문에 시간 복잡도가 커서 그리 좋지는 않다. 그래서 그냥 five 를 5KG 봉지의 개수로 두되, 남은 KG 를 따로 변수로 둔 뒤, 이것이 3으로 나누어 떨어진다면 바로 해당 조합을 사용했다면 좋았을 것이다.

 

11050번 : 이항 계수 1

 

음... 그냥 쉽다. 팩토리얼을 구하는 함수를 하나 만들고 n!/k!(n-k)! 을 하면 된다. 그것이 이항계수니까..

 

근데 그러면 구현 문제를 푼게 아니라 그냥 공식을 적용한 것 뿐이므로 이항 정리를 통해 풀어본다.

 

내 코드(정답 이긴 함):

n,k = map(int,input().split())

def factorial(n):
    answer = 1
    for i in range(n,0,-1):
        answer *= i
    return answer

print(factorial(n) // factorial(n-k) // factorial(k))

 

gugudan님의 코드:

def combine(n, k):
    if k == 0:
        return 1
    if k == n:
        return 1
    if memo[n][k] != -1:
        return memo[n][k]
    return combine(n - 1, k - 1) + combine(n - 1, k)


N, K = [int(x) for x in input().split(' ')]
memo = [[-1 for k in range(K + 1)] for n in range(N+1)]
print(combine(N, K))

 

 

 

이로써 CLASS 2 에 있는 브론즈 문제들을 모두 마쳤다. 별로 어렵지 않았다. 어서빨리 실버 문제를 풀어보자!