알고리즘 스터디 - HackerRank : Red John is Back

문제 해석

사실 이 문제를 봤을 때 구글 번역기로 돌려도 이해하기가 힘든 문제였다. 한글로 봐도 애초에 뭘 원하는지 명확하게 이해하기가 힘들어서 많이 헤매게 되었다.

• 피해자 집의 벽 사이즈가 CxN이다.
• 여기서 C는 합성수로 1보다 큰 자연수 중에서 소수가 아닌 수로, 약수의 개수가 3개 이상이고 둘 이상의 소수를 곱한 자연수이다.
• 피해자는 Cx1, 1xC 형태의 블록을 가지고 있다.
• 특정 구성 요소로만 문이 열리는 비밀의 문이 존재하고 있다.
• 벽은 벽돌을 사용해 완전히 덮여져야 한다.
• 패트릭은 M 이하의 소수의 개수 P를 알고 싶어한다.
• 패트릭이 P를 계산하면 테레사는 Red John에게 전화해 패트릭이 정답을 말했는지 알아낼 수 있다.
• 즉, 패트릭이 소수의 개수를 구하도록 하면 된다.

이 경우에는 C = 4인 것을 가정한다.

입력

• 처음에는 테스트 케이스의 개수 t를 받음
• 다음 줄 부터 각 t마다 해당되는 n을 입력받음
• n은 4xn의 요소로 벽의 세로의 길이가 4이어야 하면서 n=3일 때에는 가로의 길이일 때 만들 수 있는 요소는 1개로 1보다 작은 소수는 없어서 P=0이다.
• 그러나, n=5면 경우의 수는 3으로 3보다 작은 소수의 개수는 2개로 P=2이다.

전체 과정
1. n을 기준으로 만들 수 있는 벽의 경우의 수 M을 구함
2. M보다 작은 소수의 개수 P를 구함
3. P를 출력함

1. M을 어떻게 구해야할까?

1. 눕혀진 것이 아예 없으면 M에 1 추가
2. 하나라도 눕혀져 있으면 4개를 사용해야 함

n = 3일 때 4로 나누면 몫 : 0, 나머지 3
-> 이 경우 1개
n = 10 일 때 몫 : 2, 나머지 2

m = 1 선언 어차피 눕혀진 것이 없는 경우는 항상 존재하기 때문이다.
몫과 나머지로 조합을 생성
[0, 0, 1, 1]

조합을 구해야 하므로 가능한 케이스는 2가지 이다.

case 1

from itertools import combinations
combinations(array, n)

case 2

def combi(n):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    
    return combi(n-1) + combi(n-4)

Hackerrank는 내장 함수만 사용가능한 경우가 있어서 case 2로 해야하고 또한, 1개를 뺄지 4개를 뺄지 여러 조합이 다르기에 case2가 더욱 직관적이고 좋다.

2. 소수의 개수를 구하는 방법

여기서는 우리가 흔히 알려져있는 "에라토스테네스의 체"를 활용해 해보도록 하겠다.

소수 찾는 알고리즘

def SieveOfEratosthenes(n):
    prime = [True for i in range(n+1)]

    p = 2
    while(p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    c = 0
    
    for p in range(2, n):
        if prime[p]:
            c += 1
    return c

알고리즘 코드

def combi(n):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    
    return combi(n-1) + combi(n-4)

def SieveOfEratosthenes(n):
    prime = [True for i in range(n+1)]
    if n <= 2: return 0
    p = 2
    while(p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    c = 0
    
    for p in range(2, n):
        if prime[p]:
            c += 1
    return c

def redJohn(n):
    return SieveOfEratosthenes(combi(n) + 1)

문제 해석만 잘하면 절차에 맞춰서 잘 풀수 있는 문제이지만 영어 해석부터 막혀서 힘든 문제인 것 같다.