[C언어] N 두 수의 곱으로 표현 / 큰수의 법칙

1. 정수 N이 주어졌을 때, N이 1 이상 9 이하의 두 수 a, b의 곱으로 표현될 수 있는지 판단하라.

입력 조건

· 첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다.

· 하나의 정수 N이 주어진다.(1≤N≤100)

출력 조건

· N이 1 이상 9 이하의 두 수 a, b의 곱으로 표현될 수 있으면 “Yes”, 아니면 “No”를 출력하라.

#include <stdio.h>
// 표준 입력 출력을 할 수 있게 도와주는 라이브러리 함수로, printf를 사용할 수 있게 해준다.
#include <string.h>
// 이 헤더파일에는 C 형식 문자열 (널 종료 문자열)을 다룰 수 있는 함수들을 포함하고 있다.
// 이번 문제에서는 memcpy를 사용하기 위해 헤더파일을 사용한다.

void init(); // 반환값이 없는 init 함수 선언
void Timetable(); // 반환값 없는 Timetable 함수 선언

int num[82]; // num 배열을 선언
// 9 * 9 = 81이기 때문에 0 ~ 81까지만 인덱스를 사용하면 된다.
int N; // 1 이상 9 이하의 두 수의 곱으로 찾고 싶은 수

int main (int argc, char *argv[]) {
    // 위 main 함수가 표준이다.
    // void를 쓰면 인수가 없다는 것을 알려줄 수 있다.
    int T, tc; // T, tc 정수형 변수 선언
    
    printf("T를 입력하세요. : ");
    scanf("%d", &T); // T를 입력한다.
    
    for (tc = 1; tc <= T; tc++) { // T번 입력하면 for문 탈출
        init(); // 초기화 및 초기 입력
        Timetable(); // 구구단
        printf("%d %s\n", tc, N == 1? "No" : "Yes"); // N = 1이면 No를 출력, N = 0이면 Yes 출력
    }
    
    return 0; // 현재 실행 중인 함수를 끝낸다.
}

void init() {
    N = 0; // N = 0으로 초기화한다.
    memset(num, 0, sizeof(num)); // num 배열의 메모리의 특정한 블록을 복사한다.
    // memset 함수를 사용하면 메모리의 내용을 원하는 크기만큼 특정값으로 설정할 수 있다.
    printf("N을 입력하세요. : ");
    scanf("%d", &N); // N을 입력한다.
}
void Timetable() {
    for (int i = 1; i <= 9; i++) { // i가 1부터 9까지 반복
        for(int j = 1; j <= 9; j++) { // j가 1부터 9까지 반복
            num[i * j] = 1;
            // i를 1부터 9이하, j도 1부터 9이하로 표현 가능하다면 num[N]의 값이 1이 된다.
        }
    }
    if (num[N] == 0) { // num[N]이 0이면
        N = 1; // N = 1로 선언하여 No를 출력할 수 있도록 한다.
    }
    else { // num[N]이 1이면
        N = 0; // N = 0이면 Yes를 출력할 수 있도록 한다.
    }
}

실행 결과

T를 입력하세요. : 3
N을 입력하세요. : 2
1 Yes
N을 입력하세요. : 19
2 No
N을 입력하세요. : 10
3 Yes
Program ended with exit code: 0

---

2. (그리디 알고리즘 구현문제) 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드시오.

입력 조건 

· 첫째 줄에 N(2≤N≤1,000), M(1≤M≤10,000), K(1≤K≤10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.

· 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.

· 입력으로 주어지는 K 는 항상 M 보다 작거나 같다.

출력 조건

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

#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;
            }
        }
    }
    
    first = arr[N - 1]; // 가장 큰 수
    second = arr[N - 2]; // 두 번째로 큰 수
    
    // 가장 큰 수가 더해지는 횟수 계산
    int cnt = (M / (K + 1)) * K;
    cnt += M % (K + 1);
    
    int result = 0; // 결과값 초기화
    result += cnt * first; // 가장 큰 수 더하기
    result += (M - cnt) * second; // 두 번째로 큰 수 더하기
    
    printf("결과값: %d\n", result); // 결과값을 출력한다.

    return 0; // 현재 실행 중인 함수를 끝낸다.
}

실행 결과

N을 입력하시오: 5
M을 입력하시오: 6
K를 입력하시오: 5
[1]: 3
[2]: 5
[3]: 7
[4]: 8
[5]: 6
결과값: 38
Program ended with exit code: 0

문제 해석

하나의 숫자를 연속으로 더할 수 있는 횟수는 최대 K번이다.

따라서 가장 큰 수를 K번 더하고, 두 번째로 큰 수를 한 번 더하는 연산을 반복하면 된다.

따라서 덧셈 연산이 총 M번 진행되면 계산을 종료한다.

반복문 안에서 scanf가 씹히는 현상

fflush(stdin);

    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번의 입력을 할 수 없었다. 그러한 문제를 해결하기 위해 찾은 방법이 fflush(stdin);이다.

위 코드를 작성하니 scanf 오류가 사라졌다.