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

문제 풀이

딱히 시간 복잡도나 공간 복잡도를 고려할 필요도 없이 단순한 사칙연산만 하면 충분히 통과 가능한 브론즈 문제인데 생각보다 정답 비율이 엄청 낮아서 포스팅하기로 했다.

브론즈 문제가 약 27%의 낮은 정답률을 보인다는 것은 난이도 설정이 잘못되었거나 문제에 헷갈릴만한 요소가 있어서 잘못된 방향으로 제출하여 많은 오답을 기록하기 때문이라 생각한다.

그래서 필자가 추측컨대 아마 감독관 수의 최솟값을 구해야 하는 문제에서 "총감독관은 오직 1명만 있어야 하고" 란 지문이 오히려 헷갈리게 했을 가능성이 있는 것 같다.

이 말이 총감독관은 2명 이상 있으면 안 된다고 판단하여 "0명도 가능하지 않나?" 란 생각이 들게 할 수 있는 것 같다.

따라서 "총감독관은 반드시 1명 있어야 하고" 로 바뀌었으면 단번에 맞춰서 정답 비율이 더 높진 않았을까 하는 아쉬움이 남았다.

또한 이 문제에 대해 시간 초과가 뜨는 경우가 종종 있던데 시험장의 수와 응시자의 수가 최대 100만이므로 수학 연산으로 답을 도출해야지 반복문을 통해 일일이 빼는 경우엔 절대 2초 안에 연산이 불가능하다는 것을 생각해야 한다.

방향성만 제대로 잡는다면 상당히 쉬운 문제라 서론이 길었는데 전체 코드를 통해 설명하도록 하겠다.

n=int(input())
n_cnt=list(map(int,input().split()))
b,c=map(int,input().split())
res=0
for i in range(n):
    n_cnt[i]-=b
    res+=1
    if n_cnt[i]>0:
        if n_cnt[i]%c==0:
            res+=(n_cnt[i]//c)
        else:
            res+=(n_cnt[i]//c+1)

print(res)

난이도 답게 상당히 짧고 간결한 코드가 나왔다.

4번째 줄까지는 필요한 입력을 받고 정답으로 출력할 변수를 초기화하는 코드다.

5번째 줄에서 for문으로 전체 시험장을 반복하며 반드시 총감독관이 있어야 하기에 총감독관이 감시할 수 있는 응시자 수를 빼고 res 변수를 카운트했다.

그 뒤에 만약 남은 응시자 수가 부감독관이 감시할 수 있는 응시자 수의 배수라면 나눈 몫을 카운트했고 배수가 아니라면 몫과 더불어 1만큼 더 큰 숫자를 카운트했다.

그 뒤에 카운트 한 숫자만큼 출력하면 통과할 수 있다.

단순 사칙연산 문제로 아주 쉬운 편이었지만 헷갈릴 수 있는 부분이 있어 입력과 출력 예제를 유심히 봐야 하는 문제였다.

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

문제 풀이

최대 공약수와 최소 공배수에 관한 수학 문제이다.

문제에 들어가기 앞서 최대 공약수와 최소 공배수에 대한 관계와 최대 공약수를 구하는 방법인 유클리드 호제법을 알고 있어야 수월하게 풀 수 있다.

간단하게만 설명하자면 두 수 A, B가 있을 때 동시에 나눠서 나머지가 0이 되는 가장 큰 수를 최대 공약수라 하고 A의 배수, B의 배수 중 가장 작은 수를 최소 공배수라 한다.

여기까지는 누구나 알고 있지만 관계에 대해서 이해해야 보다 수월하게 풀 수 있다.

최대 공약수를 c, 최소 공배수를 d라 하고 A를 c로 나눈 몫을 a, B를 c로 나눈 몫을 c로 한다면 a와 b는 서로소 관계(1을 제외한 공약수가 없는 관계)가 된다.

따라서 a x b x c = d 가 성립하기 때문에 이를 자유자재로 이용할 수 있어야 한다.

또한 유클리드 호제법은 두 수가 있을 때 큰 수를 작은 수로 나눈 나머지가 0이 될 때까지 반복하여 최대 공약수를 구하는 방식이다.

전체 코드에서 구현 방법을 보면 이해될 것이다.

def gcd(num1,num2):
    if num2%num1==0:
        return num1
    else:
        return gcd(num2%num1,num1)
a,b=map(int,input().split())
b=b//a
res=[]
for i in range(1,b+1):
    if b%i==0:
        if i<b//i:
            if gcd(i,b//i)==1:
                res.append([i*a+(b//i)*a,i*a,(b//i)*a])
        else:
            if gcd(b//i,i)==1:
                res.append([i*a+(b//i)*a,(b//i)*a,i*a])
if len(res)>0:
    res.sort(key=lambda x:x[0])
    print(res[0][1],res[0][2])

먼저 유클리드 호제법을 사용하는 최대 공약수를 구하는 함수를 gcd로 선언했다.

gcd는 최대 공약수(Greatest Common Divisor)의 약자이기 때문인데, 이처럼 코드를 작성할 때는 해당 변수가 무엇을 뜻하는지, 해당 함수가 어떤 기능을 하는지 의미하는 이름으로 짓는 게 차후에 코드를 이해하기 편해서 좋다.

num2가 num1보다 더 큰 수이고 함수를 보면 알 수 있듯이 큰 수를 작은 수로 나눴을 때 나머지가 0이면 작은 수를 리턴, 아니라면 나머지와 나눴던 작은 수를 매개변수로 재귀 호출한다.

이렇게 반복하면 최대 공약수를 얻을 수 있다.

7번째 줄에서 b를 a로 나눈 몫으로 저장하는 이유는 최소 공배수에서 최대 공약수를 없애고 서로소인 두 수의 곱만 고려하기 위해서다.

만약 서로소 관계인 두 수를 구한다면 각 각 최대 공약수를 곱해서 출력하면 답을 구할 수 있을 것이기 때문이다.

8번째 줄의 res 리스트는 서로소인 두 수와 두 수의 합을 저장하는 용도다.

문제에서 분명 조건에 부합하는 자연수 쌍은 여러 개 있을 수 있는데 두 자연수의 합이 최소인 경우를 출력하라 했으니 합을 기준으로 정렬하여 가장 작은 경우를 출력하면 될 것이다.

따라서 9번째 줄에서 1부터 b까지 반복을 하는데 i로 b를 나눈 나머지가 0이면 두 수의 곱으로 나타낼 수 있는 숫자고 두 번째 if문은 더 큰 수를 gcd 함수의 두 번째 인자에 넣기 위한 조건문이다.

또한 gcd 함수의 반환 결과가 1이라면 두 수가 서로소 관계이므로 두 수의 합과 두 수를 최대 공약수를 곱해서 res 리스트에 넣었다.

반복문이 종료되면 res 리스트를 두 수의 합을 기준으로 오름차순 정렬하고 첫 번째 원소에 들어가 있는 두 수를 출력하면 통과한다.

문제를 통과하긴 했지만 조금 더 생각하면 탐색하는 범위를 절반 정도로 줄일 수 있을 것 같다.

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

문제 풀이

브론즈 문제 치고 정답 비율이 24%로 엄청 낮은 통계였다.

왜 그런가 싶어서 문제를 자세히 봤더니 아마 생각난 방식 그대로 제출한다면 시간 초과가 날 것 같단 생각이 들었다.

문제 자체는 단순하게 데이터의 개수만큼 컴퓨터 대수인 10개를 나눈 나머지를 출력하고 0만 10으로 변환하면 되는데 여기서 문제는 데이터의 개수가 a^b 만큼 들어오고 a는 100 미만, b는 1000000 미만의 자연수이므로 총 100000000(1억) 개의 데이터가 될 수 있으며 심지어 테스트 케이스도 입력받기 때문에 단순하게 제곱수를 통한 구현은 시간 초과가 날 가능성이 높았기 때문이다.

혹시나 해서 그대로 구현하여 제출했더니 역시 시간 초과가 났다.

n=int(input())
for i in range(n):
    a,b=map(int,input().split())
    print(a**b%10)

따라서 시간을 줄일 수 있는 방식을 생각해야 했고 일의 자리가 나올 수 있는 숫자들을 구해서 해당 개수만큼 나눈다면 어느 정도 정답에 근접할 것이라 생각했다.

다음은 통과한 전체 코드이다.

n=int(input())
for i in range(n):
    a,b=map(int,input().split())
    if a==1:
        print(1)
    else:
        last=a%10
        last_num=[last]
        sum_last=(last**2)%10
        while sum_last not in last_num:
            last_num.append(sum_last)
            sum_last=(sum_last*last)%10
        if last_num[(b-1)%len(last_num)]==0:
            print(10)
        else:
            print(last_num[(b-1)%len(last_num)])

먼저 4번째 줄에서 if문을 쓴 이유는 a가 1이라면 b가 어떤 숫자가 나와도 데이터 개수는 1개이므로 무조건 1이 나올 수밖에 없기 때문에 처리했다.

a가 1이 아닌 나머지의 경우엔 일의 자리를 구해서 리스트에 저장하고 동일한 숫자가 나오기 전까지 a를 곱하여 일의 자리를 계속해서 추가한다.

10으로 나누기 때문에 최대 10개가 나올 수 있으며 0은 10으로 치환해야 한다는 것을 잊으면 안 된다.

해당 반복문이 종료되면 인덱스는 0부터 시작하기 때문에 b-1을 last_num의 길이(일의 자리에 나올 수 있는 숫자들)로 나누고 해당 숫자가 0이면 10으로 치환, 아니면 해당 숫자를 출력하면 통과한다.

역시 구현 자체가 어려운 문제는 아니라 단순하게 생각해서 제출한 경우가 많아 정답 비율이 낮게 나온 것 같다.