[경시대회] 소믈리에 구름이

---

문제 정리

• 구름이가 가진 모든 와인 용량은 N-1로 통일
  • 7잔 이라면 와인의 용량은 6임
• 한 병의 와인을 따를 시 N-1개 잔을 각 잔에 정확히 1만큼씩 따라야함
  • 7잔 이라면 7잔 중 6잔에 1만큼 씩 따라야함

문제 접근 방법 1

• qsort 후 첫 번째 인덱스 제외한 나머지 인덱스 증가
  • 내림차순으로 정렬
• 모든 인덱스가 같은지 검사하는 check 함수 작성해서 모든 인덱스가 같다면 종료

---

1차 시도

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

int compare(const void*a, const void*b) {
	return(*(int*)b - *(int*)a); //내림차순 
}

int check(int *arr,int n,int a){
	for(int i = 0 ; i < n ; i++){
		if(arr[i] != a)
			return -1;
	}
		return 1;
}

int main() {
	int n;

	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++) { // 와인 용량 입력
		scanf("%d", &arr[i]);
	}

	// 용량 n-1로 맞추기
	// n-1 개 잔을 골라 각 잔에 1만큼씩 따른다.
	
	int count = 0;
	
	for(int k = 0 ; k < n*n ; k++){
		qsort(arr, n, sizeof(int), compare);
		for(int i = 1 ; i < n ; i++){
			arr[i]++;
		}
		count++;
		if(check(arr,n,arr[0])==1)
			break;
	}

	
	printf("%d", count);
	free(arr);

	return 0;
}

• 문제에서 주어졌던 1, 2번의 테스트 케이스는 통과하였지만 나머지 테스트 케이스에서 TimeOut이 발생함
• TimeOut이 발생한 이유
  • 가장 먼저 든 생각은 N의 범위 때문임
    • 1 ≤ N ≤ 200,000
    • N이 최악일 경우의 알고리즘을 구현하는 것이 중요해 보임
  • 시간복잡도 고려하지 않음
    • 위와 비슷한 이유이기도 하고 보다 나은 알고리즘이 있을 것이라 생각됨

 

2차 시도

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

int compare(const void*a, const void*b) {
	return(*(int*)b - *(int*)a); //내림차순 
}

int check(int *arr,int n,int a){
	for(int i = 0 ; i < n ; i++){
		if(arr[i] != a)
			return -1;
	}
	return 1;
}

int main() {
	int n;

	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++) { // 와인 용량 입력
		scanf("%d", &arr[i]);
	}

	// 용량 n-1로 맞추기
	// n-1 개 잔을 골라 각 잔에 1만큼씩 따른다.
	
	int count = 0;
	
	for(int j = 0 ; j < n ; j++){
		for(int k = 0 ; k < n ; k++){
			qsort(arr, n, sizeof(int), compare);
			if(check(arr,n,arr[0])==1){
				break;
			}
			for(int i = 1 ; i < n ; i++){
				arr[i]++;
				if(i==n-1){
					count++;
				}
			}
		}
	}

	
	printf("%d", count);
	free(arr);

	return 0;
}

• 초기 정렬 과정을 이중 for 문으로 개선하였음
• 테스트 3번 케이스 통과

문제점

• 결과적으로 삼중 for문임
• 시간 복잡도는 O(n^3)

 

3차 시도

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
int compare(const void* a, const void* b) {
    return (*(int*)b - *(int*)a); // 내림차순
}

int check(int* arr, int n, int a) {
    for (int i = 0; i < n; i++) {
        if (arr[i] != a)
            return -1;
    }
    return 1;
}

int main() {
    int n;

    scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    int count = 0;

    while (check(arr, n, arr[0]) != 1) {
        qsort(arr, n, sizeof(int), compare);
        for (int i = 1; i < n; i++) {
            arr[i]++;
        }
        count++;
    }

    printf("\n필요한 최소 와인 잔 : %d", count);
    free(arr);

    return 0;
}

• 반복 탈출 조건을 check 함수를 이용함
• 4번 케이스까지 성공

문제점

• timeout 발생

문제 해결

• 예제를 계속 보면서 떠오른 아이디어
  • 와인의 총 용량에서 입력된 와인 잔을 뺀다면 필요한 와인 잔이 나오지 않을까?
  • 7 [1 5 2 1 2 2 2] 에서 (총 용량)15 - (와인 잔)7 = (필요한 와인 잔)8
  • 7 [2 2 3 2 5 5 1] 에서 (총 용량)20 - (와인 잔)7 = (필요한 와인 잔)13
    • 예제와 같음
• 범위 고려하여 long long int 사용

4차 시도

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
typedef long long ll;
int main() {
    int n;
    scanf("%d", &n);

    ll* wine_capacity = (ll*)malloc(sizeof(ll) * n);

    for (int i = 0; i < n; i++) {
        scanf("%lld", &wine_capacity[i]);
    }

    ll total_wine = 0;

    for (int i = 0; i < n; i++) {
        total_wine += (ll)wine_capacity[i];
    }

    ll min_operations = total_wine - (ll)n;

    printf("%lld", min_operations);

    free(wine_capacity);

    return 0;
}

 

• 90% 이상 성공하였음…
• 억지 코드 같지만 위 알고리즘으로 문제 해결 가능할 듯 싶음