[BAEKJOON 1463] 1로 만들기

# 문제 조건

소수 찾기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

203068

96061

76868

47.173%

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1 복사

4
1 3 5 7

예제 출력 1 복사

3

 

# 작성한 코드

 

n = int(input())

숫자 n 입력받고

d = [0] * (n+1)  # 연산 횟수가 0

n+1 크기의 리스트 d를 생성 / 모든 요소 0으로 초기화

for i in range(2, n+1):

    d[i] = d[i-1] + 1

2부터 n까지 반복함 / 1은 연산을 필요로 하지 않기 때문에 2부터 시작

    if i % 3 == 0:  # 3으로 나눠떨어질 때

        d[i] = min(d[i], d[i//3]+1)

숫자 i가 3으로 나눠떨어질 때,

나눈 후 숫자 i//3을 1로 만들기 위한 '최소 연산 횟수+1'과 '최소 연산 횟수' 중 더 잓은 값 채택!

    if i % 2 == 0:  # 2로 나눠떨어질 때

        d[i] = min(d[i], d[i//2]+1)

숫자 i가 2로 나눠떨어질 때,

나눈 후 숫자 i//2을 1로 만들기 위한 '최소 연산 횟수+1'과 '최소 연산 횟수' 중 더 잓은 값 채택!

print(d[n])  

n을 1로 만들기 위한 최소 연산 횟수 출력

 

# if n = 55

터미널 결과

초기 숫자는 55

1. 첫 번째 연산으로 55에서 1을 빼면 54 -> 연산 횟수 1회

2. 54는 3으로 나눠 떨어지므로 54를 3으로 나눠 18을 만듦 -> 연산 횟수 2회

3. 18 역시 3으로 나눠 떨어지므로 18을 3으로 나눠 6을 만듦 -> 연산 횟수 3회

4. 6을 3으로 나누면 2 -> 연산 횟수 4회

5. 2를 2로 나누면 1 -> 연산 횟수 5회

 

55 -> 54 -> 18 -> 6 -> 2-> 1

따라서, 초기값 55를 1로 만들기 위한 최소 연산 횟수는 '5'회가 된다.

 

* 다이나믹 프로그래밍 사용 이유: 각 단계에서 최적의 결정(이 문제에서는 최소 연산 횟수)를 기록하고

   이를 바탕으로 다음 단계의 최적 결과를 도출할 수 있다.

# 최종 코드

n = int(input())

# DP - 다이나믹 프로그래밍

d = [0] * (n+1)  # 연산 횟수가 0

for i in range(2, n+1):

    d[i] = d[i-1] + 1

    if i % 3 == 0:  # 3으로 나눠떨어질 때

        d[i] = min(d[i], d[i//3]+1)

    if i % 2 == 0:  # 2로 나눠떨어질 때

        d[i] = min(d[i], d[i//2]+1)

print(d[n])  

위 코드는 다이나믹 프로그래밍으로 접근하여 풀었음