모든 답안은 모범 답안이 아닌 예시 답안입니다. 제가 드리는 답안 중에 종종 숏코딩이 있을 수 있습니다. 숏코딩은 가독성 측면에서는 매우 안좋기 때문에 자제 해야하지만, 라이브러리를 익히거나 여러 아이디어를 줄 수 있기에 적절하게 수용하는 것이 중요합니다.
이번 과제의 핵심은 구현 연습과 수학적 지식 활용 입니다.
A. 수학은 체육과목 입니다 2
해설 및 포인트
구현 중에서 대표적으로 어떤 과정을 시뮬레이션 하는 문제입니다.
이 문제에서는 시뮬레이션을 진행하기에는 N 제한이 매우 큽니다. 그래서 N이 큰 경우는 output이 규칙적이라는 성질을 사용합니다.
이런 류의 문제는 사이클(Cycle)을 찾는 것이 중요합니다.
Cycle의 포인트는 2가지 입니다.
- Cycle의 시작점
- Cycle의 주기
여기서는 1번에서 시작해서 9번에 다시 1번으로 돌아오는 것을 확인할 수 있습니다. 그렇다면 여기서 사이클 시작은 1, 사이클 주기는 9-1=8 임을 알 수 있습니다. 그렇다면 초기 시작점과 사이클 시작은 같으므로 우리가 원하는 손가락은 N을 8로 나눈 나머지만큼 과정을 진행하면 됩니다.
source code
- 보통 시작이 1이면 나머지 연산이 어려운 경우가 있습니다. -1을 하여 0-index로 변환하고, 최종 답안을 +1 하는 방법이 가장 좋습니다.
- 이 문제는 약지를 기준으로 대칭이라는 성질을 가지고 있으므로, 다음과 같이 코드로 작성가능합니다.
- 또는 1, 2, 3, 4, 5, 6, 7 8에 대해 조건문을 작성해도 됩니다.
N = int(input())-1
print(min(8-n%8, n%8)+1)
B. 주사위 네개
해설 및 포인트
주사위 3개와 거의 동일한 문제입니다. 다만 수의 개수가 1개 늘었으므로 처리해야하는 케이스가 늘었습니다.
수의 개수를 카운팅하는 방법은 다음 방법들이 있을 수 있습니다.
dict(또는defaultdict)를 사용하여 countcollections라이브러리의Counter함수 사용- 정렬 후, 직접 counting
개인적으로는 3번을 선호합니다. 그렇다면 정렬 후에는 어떻게 각 케이스를 처리할 수 있을까요?
- 4개 동일 :
len(set(lst))==1set 원소의 개수가 1개 - 3개 동일 :
len(set(lst))==2 && lst[1] == lst[2]set 원소의 개수가 2개, 그리고 중앙 2개 동일 - 2, 2개 동일 :
len(set(lst))==2이고 3개 동일 아님 - 2개 동일 : 반복문으로 이웃하는 2개 비교
- 1개 동일 : max값
자세한 건 코드로 살펴봅시다.
source code
max + list comprehension을 사용하면 다음과 같이 출력할 수 있습니다.
def money():
lst = sorted(list(map(int, input().split())))
if len(set(lst)) == 1: return lst[0] * 5000 + 50000
if len(set(lst)) == 2:
if lst[1] == lst[2]: return 10000 + lst[1] * 1000
return 2000 + (lst[1] + lst[2]) * 500
for i in range(3):
if lst[i] == lst[i+1]: return 1000 + lst[i] * 100
return lst[-1] * 100
N = int(input())
print(max(money() for i in range(N)))
C. 이름궁합 테스트
해설 및 포인트
이제 조금씩 복잡한 문제가 나오기 시작합니다. 이런 문제는 문제의 전체적인 과정을 잘 설계하는 과정이 중요합니다.
이 문제는 다음 3단계로 구성할 수 있습니다. (입력과 출력 제외)
- 문자열 합치기
- 문자열 수치로 변환하기
- 길이 X 수열을 길이 X-1 수열로 변환
문제가 복잡해지면 각 과정을 함수로 작성하는 것을 추천하고, 간단한 과정이면 main 함수(전체 진행 코드) 내에서 직접적으로 구현하면 됩니다.
2번 과정의 수치로 변환하기에서는 수치(획수)를 미리 배열로 전환 하는 방법이 가장 편리하고 좋습니다. (PS 및 코테는 종종 이런 류의 노가다 작업이 있을 수 있습니다.)
3번 과정에서는 수열을 다음 수열로 만드는 함수를 만들어도 되지만, 생각해보면 수열에서 뒤의 원소를 앞에 더하는 방식으로 부분 수열을 쉽게 만들 수 있다는 점을 관찰할 수 있습니다. 이런 과정은 후에 동적계획법(Dynamic Programming, DP) 에서도 많이 활용되니 그 느낌을 알아두도록 하세요.
이 문제에서는 수열을 합치는 과정에서 약 \(O((N+M)^2)\)임을 알 수 있습니다.
source code
N, M = map(int, input().split())
A, B = input().split()
alp = [3, 2, 1, 2, 4, 3, 1, 3, 1, 1, 3, 1,
3, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1]
AB = ''
min_len = min(N, M)
for i in range(min_len): AB += A[i] + B[i]
AB += A[min_len:] + B[min_len:]
lst = [alp[ord(i)-ord('A')] for i in AB]
for i in range(N+M-2):
for j in range(N+M-1-i):
lst[j] += lst[j+1]
print(f"{lst[0]%10*10 + lst[1] % 10}%")
D. 소수 단어
해설 및 포인트
이 문제는 총 2가지 step이 있습니다.
- 단어를 수로 변환
- 소수 판별
단어를 수로 변환하는 과정이 가장 번거로울 것 같습니다.
번거롭지만 소문자의 수는 ord(x)-ord('a')+1, 대문자의 수는 ord(x)-ord('A')+27 로 변환하면 된다는 포인트만 알면 쉽게 할 수 있습니다.
소수 판별은 이전에 배운 \(O(\sqrt{N})\) 방법을 사용해봅시다
source code
- 저는 이 코드로 제출했는데 정답 처리가 되었습니다. (사실 이 경우에는
a가 입력으로 들어오면 1이기 때문에 소수가 아닌데 말이죠.) - 이런 경우는 나중에 사이트에 데이터 요청을 하면, 데이터가 추가되고 재채점이 이뤄집니다.
S = input()
ret = sum([ord(i)-ord('a')+1 if ord('a') <= ord(i)
<= ord('z') else ord(i)-ord('A')+27 for i in S])
def isPrime(n):
p = 2
while p*p <= n:
if n % p == 0: return False
p += 1
return True
print(f"It is{'' if isPrime(ret) else ' not'} a prime word.")
E. 최대공약수와 최소공배수
해설 및 포인트
문제 자체가 정의 입니다. 수업 및 자료 바탕으로 코드를 진행해도 되고, 또는 math 라이브러리의 gcd 함수를 사용해봅시다.
source code
from math import gcd
A, B = map(int, input().split())
g = gcd(A, B)
print(g)
print(A*B//g)
F. 타일 위의 대각선
해설 및 포인트
이 문제는 최대공약수의 대표적인 문제 중 하나입니다.
케이스는 2가지로 나뉩니다.
- 가로, 세로가 서로소인 경우
- 가로, 세로의 최대공약수가 1이상인 경우
2의 경우는 생각해보면 1의 확장임을 알 수 있습니다. 최대공약수 단위로 반복되는 사실은 그려보면 알 수 있습니다.
그렇다면 가로, 세로가 서로소인 경우의 지나치는 사각형의 개수는 몇 개일까요?
그림을 그려보면 다음과 같은 규칙을 알 수 있습니다.
- 가로 교차점 개수 (가로 길이) + 세로 교차점 개수 (세로 길이) - 1
그리고 여기서 연장선으로 최대공약수가 g라면
- 가로 길이(g * 단위 사각형 가로 길이) + 세로 길이(g * 단위 사각형 세로 길이) - g
대표적인 유형이니 암기합시다.
source code
from math import gcd
A, B = map(int, input().split())
g = gcd(A, B)
print(A+B-g)