[C언어] 큰수의 법칙, 최소 연산 사용 횟수 구하는 법

1. (그리디 알고리즘 구현문제) 다양한 수로 이루어진 배열이 있을 때 주어진 수들 중에서 M개를 선택한 후 그 수들을 더하여 가장 큰 수를 만드시오.( 단, 특정 수가 K번을 초과해서 더해질 수 없어야 함.)

입력 조건

• 첫째 줄에 N(2≤N≤1,000), M(1≤M≤10,000), K(1≤K≤10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K 는 항상 M 보다 작거나 같다.

출력 조건

• 첫째 줄에서 구현한 큰 수의 법칙에 따라 더해진 답을 출력한다.

입력예시

5 8 3

2 4 5 4 6

 

출력값

41

문제 해결 과정

입력 값 중 가장 큰 수와 두 번째로 큰 수만 필요하다. 특정 수를 더할 수 있는 횟수는 최대 K번이므로 시행 횟수가 M이 될 때 까지 가장 큰 수를 K번 더하고 다음으로 큰 수 또한 K번을 반복하면 된다.

 

아래 코드와 같이 0을 입력해보니 반복문이 제대로 실행되지 않았다.

    for (int s = 0; s < N; s++) {
        int x;
        printf("O");
        scanf("%d", &x);
        arr[s] = x;
    }

반복문이 제대로 실행되는 것 같지가 않아서

출력문 하나를 써서 반복문을 실행보니깐

N, M, K를 순서대로 입력하시오: 5 8 3
OOO

이렇게 출력문이 3번 출력되고 scanf 입력이 뜬 것이었다. 그래서 총 3번의 입력만 되고,

2번의 입력을 할 수 없었다.

 

반복문 안에서 scanf가 씹히는 현상이 발생하여 인터넷 검색을 이용하여 fflush(stdin);을 사용하면 현재 발생한 반복문 오류가 해결된다고 나와있었다. fflush(stdin);을 작성하니 scanf 오류가 사라졌다.

코드

#include <stdio.h> // 표준 입력 출력을 할 수 있게 도와주는 라이브러리 함수로, printf를 사용할 수 있게 해준다. 
int main(void) 
{ 
	int N, M, K; int arr[1000]; 
  int first, second; 
  int i, j, tmp = 0; 
  // N, M, K를 공백으로 구분하여 입력받는다. 
    
  printf("N을 입력하시오: "); 
  scanf("%d", &N); // 입력 숫자 횟수
    
  printf("M을 입력하시오: "); 
  scanf("%d", &M); 
    
  printf("K를 입력하시오: "); 
  scanf("%d", &K); // N개의 수를 공백을 기준으로 구분하여 입력받는다. 
    
  for (int i = 0; i < N; i++) 
  { 
    int x; 
    fflush(stdin); // 입력 버퍼 지우기 함수 
    printf("[%d]: ", i + 1); 
    scanf("%d", &x); 
    arr[i] = x; 
  } 
  
  // 입력 받은 수를 내림차순 정렬 
  for (i = 0; i < N; i++) 
  { 
    for (j = i; j < N - 1; j++) 
    { 	// 기준 숫자가 있기 때문에 N - 1 
      if (arr[j] < arr[i]) 
      { 
        tmp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = tmp; 
      } 
    } 
  } 
  
  int result = 0; // 결과값 초기화 
  
  // 제일 큰 수를 K번 더하고, 그다음 수를 K번 더하고,
  // 그렇게 반복해서 M이 될 때까지 반복한다.
  for (i = 1; i * K <= M; i++)
  {
    for(j = 0; j < K; j++)
    {
      result += arr[N - i];
    }
  }
  result += (M % K) * arr[N - i];
  
  printf("결과값: %d\n", result); // 결과값을 출력한다. 
  
 return 0; // 현재 실행 중인 함수를 끝낸다. 
}

실행 결과

N을 입력하시오: 5
M을 입력하시오: 8
K를 입력하시오: 3
[1]: 2
[2]: 4
[3]: 5
[4]: 4
[5]: 6
결과값: 41

6 + 6 + 6 + 5 + 5 + 5 + 4 + 4 = 41

N을 입력하시오: 4
M을 입력하시오: 7
K를 입력하시오: 3
[1]: 1
[2]: 2
[3]: 3
[4]: 2
결과값: 17

3 + 3 + 3 + 2 + 2 + 2 + 2 = 17

N을 입력하시오: 4
M을 입력하시오: 5
K를 입력하시오: 2
[1]: 1
[2]: 6
[3]: 2
[4]: 3
결과값: 20

6 + 6 + 3 + 3 + 2 = 20

---

2. 정수 N이 주어졌을 때, 다음과 같은 연산 4개를 적절히 사용해서 1을 만들려고 한다. 다음 연산을 사용하는 횟수를 최소화해서 1을 만들고 그 연산 사용 횟수를 출력하시오.

(1) N이 5로 나누어떨어지면, 5로 나눈다.

(2) N이 3로 나누어떨어지면, 3로 나눈다.

(3) N이 2로 나누어떨어지면, 2로 나눈다.

(4) N에서 1을 뺀다.

문제 해결 과정 

컴파일하고 프로그램이 잘 돌아가는지 확인하기 위해서 16과 8을 N으로 했을 때 최소 시행 횟수 오류가 발생했다. 이것을 어떻게 해결할지 생각해보아야한다. while문에 들어가기 전에 -1을 한 시행 횟수와 -1을 하지 않은 시행 횟수를 구해서 최소 시행 횟수를 비교하는 방법이 가능할 지 해보아야 한다. N을 n1, n2로 나누고 실행횟수도 i1, i2로 나누어서 풀어보고 i1과 i2를 비교하여 더 작은 값을 최소 시행 횟수로 지정하는 방법을 채택했다.

코드

#include <stdio.h>
// 표준 입력 출력을 할 수 있게 도와주는 라이브러리 함수로, printf를 사용할 수 있게 해준다. 

int main(void)
{
    int N; 
    int i;
    int i1 = 0;
    int i2 = 0; 
    // i, i1, i2는 연산 횟수
    
    int n1, n2;

    printf("N을 입력하세요: ");
    scanf("%d", &N);

    n1 = N; // 5의 배수, 3의 배수가 아닌 조건을 만족할 때 -1을 하고 구하는 값
    n2 = N; // 5의 배수, 3의 배수가 아닌 조건을 만족하지 않을 때 값

    if (n1 % 5 != 0 && n1 % 3 != 0)
    {
        n1 -= 1; i1++;
    }

    while (1)
    {
        if (n1 % 5 == 0) // 5로 나누어 떨어질 때 
        {
            n1 /= 5; i1++; // n1을 5로 나누고, i1 시행 횟수 증가
        }

        else if (n1 % 3 == 0) // 3으로 나누어 떨어질 때
        {
            n1 /= 3; i1++; // n1을 3로 나누고, i1 시행 횟수 증가
        }

        else if (n1 % 2 == 0) // 2로 나누어 떨어질 때
        {
            n1 /= 2; i1++; // n1을 2로 나누고, i1 시행 횟수 증가
        }

        else
        {
            n1 -= 1; i1++; // 위 조건을 만족하지 못할 때, n1을 -1 해준다.
        }

        if (n1 == 1)
        {
            break; // n1이 1이 될 때 while문 종료
        }
    }

    while (1)
    {
        if (n2 % 5 == 0) // n2가 5로 나누어 떨어질 때
        {
            n2 /= 5; i2++; // n2를 5로 나누고, i2 시행 횟수 증가
        }

        else if (n2 % 3 == 0) // n2가 3로 나누어 떨어질 때
        {
            n2 /= 3; i2++; // n2를 3로 나누고, i2 시행 횟수 증가
        }

        else if (n2 % 2 == 0) // n2가 2로 나누어 떨어질 때
        {
            n2 /= 2; i2++; // n2를 2로 나누고, i2 시행 횟수 증가
        }

        else
        {
            n2 -= 1; i2++; // 위 조건을 만족하지 못할 때, n2를 -1 해준다.
        }

        if (n2 == 1)
        {
            break; // n2가 1이 될 때 while문 종료
        }
    }

    // i2가 i1보다 작을 때
    if (i1 > i2)
    {
        i = i2;
    }
    // i1이 i2보다 작을 때 
    else if (i2 > i1)
    {
        i = i1; 
    }

    printf("연산횟수는 %d회 입니다.\n", i); // 연산 횟수 실행
  
    return 0; // 함수 종료
}

실행 결과

N을 입력하세요: 8
연산횟수는 3회 입니다.

N을 입력하세요: 16
연산횟수는 3회 입니다.

N을 입력하세요: 3
연산횟수는 1회 입니다.

N을 입력하세요: 13
연산횟수는 4회 입니다.

N을 입력하세요: 13
연산횟수는 4회 입니다.