코딩문제 풀기(C) - 34 (1로 만들기)

Alope·2024년 7월 13일

코딩문제

코딩문제 풀기(C언어)

목록 보기

34/44

안녕하세요!

34번째 문제입니다.

이번 글 역시 푸는 방식은 동일합니다!
1. 문제선택 및 설명
2. 문제접근 (알고리즘)
3. 문제풀기 (코딩하기)
4. 성공 (실패 시 2번)

1. 문제선택

이번 문제 역시 백준에 있는 문제입니다.
https://www.acmicpc.net/problem/1463 - 문제링크

문제설명 - 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

즉, 주어진 숫자를 3으로 나누고, 2로 나누고, 1을 빼면서 주어진 숫자를 1로 가장 적은 횟수를 사용해서 만들어야 합니다.

2. 문제접근 (알고리즘)

a. 숫자를 입력받는다.
b. 위 3가지 조건중 해당되는게 있으면 실행시킴 (우선순위는 아직 모르겠음)
c. 실행할 때마다 count변수로 횟수를 증가시킴
d. 입력받은 숫자가 1이 되면 최종 count 출력

3. 문제풀기

(코딩하고 오겠습니다...) - 34분

#include <limits.h>
#include <stdio.h>

int min(int a, int b) { return (a < b) ? a : b; }

int main(void) {
  int n;
  scanf("%d", &n);

  int dp[n + 1];
  dp[1] = 0; // 1을 1로 만드는 데 필요한 연산 횟수는 0

  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + 1; // 1을 빼는 경우
    if (i % 2 == 0) {
      dp[i] = min(dp[i], dp[i / 2] + 1); // 2로 나누는 경우
    }
    if (i % 3 == 0) {
      dp[i] = min(dp[i], dp[i / 3] + 1); // 3으로 나누는 경우
    }
  }

  printf("%d\n", dp[n]);
  return 0;
}

최종코드입니다.
결론부터 말씀드리자면 제 코드가 아니라, gpt한테 물어본 코드입니다.

#include <stdio.h>
#include <string.h>
#include <math.h>


int main(void) {

    int n;
    int compare[3];
    int count = 0;

    scanf("%d", &n);

    while(1){

        if(n == 1){
            count++;
            break;
        }
        
        for(int i=0; i<3; i++){
            if(i==0){
                compare[0] = n/3;
            }
            if(i==1){
                compare[1] = n/2;
            }
            if(i==2){
                compare[2] = n-1;
            }
        }

            if(n-1%3 == 0){
                n = compare[2];
            } else if(n%3 == 0){
                n = compare[0];
            } else if (n%2 == 0){
                n = compare[1];
            } else{
                n = compare[2];
            }

        count++;
        if(n==1) break;
        
    }

    printf("%d\n", count);
    
    
    return 0;
}

이게 제가 생각해서 푼 문제인데, 도저히 어떤 상황에서 3으로 나누는게 좋은지 2로 나누는게 좋은지 1로 빼는게 좋은지 감이 안잡히더라구요. 그래서 3가지의 값을 가지고 있는 배열을 가지고 비교를 하면서, 풀려 했는데... 와... 진짜 감이 안잡히더라구요...

그래서 gpt한테 물어보니 동적 프로그래밍을 사용해야 한다 하더라구요...?
동적 프로그래밍... 분명히 알고리즘 수업 때 배운 내용인데, 막상 코드로 적용시켜야 한다고 하니 감이 안잡히더라구요

동적 프로그래밍 설명을 보면, "복잡한 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 피하는 효율적인 알고리즘 기법"입니다.
설명을 보면 결과를 "저장"하고 "중복"을 피하는 기법이라고 합니다.
따라서 결과 코드를 보면 값을 나누어 저장하고 min(int a, int b) 함수로 넘어가 값을 비교 후 중복을 피하며 값을 저장하는 것을 볼 수 있습니다.

이번 문제를 통해 많은걸 배웠습니다..!

이번 문제는 많이 틀렸습니다...!