[BOJ] 11585 - 속타는 저녁 메뉴 (Python)

 

 

아이디어 #1

 

룰렛 칸 수의 약수 크기인 룰렛 일부로 전체 룰렛을 구성할 수 있는지 확인한다.

 

 

풀이 #1

 

공백을 없앤 문자열 roulette으로 룰렛 모양을 입력 받은 후 함수 spin을 호출하여 반환값을 출력한다.

함수 roulette에서는 for문에서 i가 N의 약수일 때 그 크기만큼 슬라이싱한 룰렛 일부(패턴)를 전체 룰렛에서 찾는다.

찾은 개수 cnt가 룰렛 전체 크기를 패턴의 크기로 나눈 값과 같으면 1/i를 반환한다.

 

확률은 패턴 개수를 전체 크기로 나눈 값인데, cnt는 N의 약수이고 N을 cnt로 나눈 값은 결국 i이므로 1/i가 기약분수다.

 

def spin():
    for i in range(1, N+1):
        if N%i == 0:
            cnt = roulette.count(roulette[:i])
            if cnt == N//i:
                return f'1/{i}'

N = int(input())
roulette = ''.join(input().split())
print(spin())

 

 

룰렛 모양이 두 번 입력되나 하나만 입력 받아도 문제를 풀 수 있다.

3번처럼 입력을 아예 안 받으면 메모리가 더 적게 사용될 줄 알았는데, 메모리가 더 많이 사용되는 점이 의외였다.

# 1.
N = int(input())
roulette = ''.join(input().split())
roulette = ''.join(input().split())
print(spin())

# 2. 1번보다 메모리가 더 적게 사용되고 더 빠른 코드
N = int(input())
input()
roulette = ''.join(input().split())
print(spin())

# 3. 1번보다는 메모리가 더 적게, 2번보다는 메모리가 더 많이 사용되나 1번과 2번보다 더 빠른 코드
N = int(input())
roulette = ''.join(input().split())
print(spin())

 

기약분수 형태로 나타내기 위해 처음에는 분모 N과 분자 cnt를 최대공약수로 나눴으나,

cnt는 N의 약수이므로 분자는 1, 분모는 패턴의 길이인 i로 반환해도 충분했다.

# 1.
def gcd(a, b):
    while b > 0:
        a = b
        b = a%b
    return a

def spin():
    for i in range(1, N+1):
        if N%i == 0:
            cnt = roulette.count(roulette[:i])
            if cnt == N//i:
                a = gcd(N, cnt)
                return f'{cnt//a}/{N//a}'

# 2. 사용 메모리와 실행 시간은 비슷하나 더 짧은 코드
def spin():
    for i in range(1, N+1):
        if N%i == 0:
            cnt = roulette.count(roulette[:i])
            if cnt == N//i:
                return f'1/{i}'

 

 

아이디어 #2

 

다른 분의 코드를 참고한 결과, find 메서드로 룰렛 패턴을 찾을 수 있었다.

 

 

풀이 #2

 

공백을 없앤 문자열 roulette으로 룰렛 모양을 입력 받은 후,

원형인 점을 고려해 roulette을 두 번 더한 문자열에서 인덱스 0 다음으로 roulette이 나타나는 인덱스를 찾는다.

찾은 인덱스가 곧 패턴의 길이이므로 분자는 1, 분모는 패턴의 길이로 하여 출력한다.

 

input()
roulette = ''.join(input().split())
print(f'1/{(roulette*2).find(roulette, 1)}')