본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[백준 알고리즘 문제풀이] 1546 평균, 4344 평균은 넘겠지 문제 풀이 및 해설

[백준 Baekjoon 알고리즘 문제 해설] 난이도: 하


정답률: 46.9%

 

[1546] 평균

제한 조건

시간 제한: 2초

메모리 제한: 128MB

문제

세준이는 기말고사를 망쳤다. 세준이는 점수를 조작해서 집에 가져가기로 했다. 일단 세준이는 자기 점수 중에 최댓값을 골랐다. 이 값을 M이라고 한다. 그리고 나서 모든 점수를 점수/M*100으로 고쳤다.

예를 들어, 세준이의 최고점이 70이고, 수학점수가 50이었으면 수학점수는 50/70*100이 되어 71.43점이 된다.

세준이의 성적을 위의 방법대로 새로 계산했을 때, 새로운 평균을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보다 크다.

출력

첫째 줄에 새로운 평균을 출력한다. 정답과의 절대/상대 오차는 10^-2까지 허용한다.

 

예제 입출력

예제 입력 예제 출력

3

40 80 60

75.00

3

10 20 30

66.666667

4

1 100 100 100

75.25

5

1 2 4 8 16

38.75

2

3 10

65.00

 


정답 비율 38.56%

정답은 전 문제보다 비율이 좀 낮네요? 어디 한 번 문제를 살펴볼까요

 

[1546번] 평균은 넘겠지

문제

대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신이 그들에게 슬픈 진실을 알려줘야 한다.

(ㅋㅋㅋㅋㅋㅋ 문제가 웃프네요..ㅎㅎ)

 

조건

시간 제한: 1초

메모리 제한: 256MB

입출력

입력:

첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 둘째 줄부터 각 테스트 케이스마다 학생의 수 N(1<=N<=1000, N은 정수)이 첫 수로 주어지고, 이어서 N명의 점수가 주어진다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력:

각 케이스마다 한 줄씩 평균이 넘는 학생들의 비율을 반올림하여 소수점 셋째 자리까지 출력한다

 

예제 입력 예제 출력

5

5 50 50 70 80 100

7 100 95 90 80 70 60 50

3 70 90 80

3 70 90 81

9 100 99 98 97 96 95 94 93 91

40.000%

57.143%

33.333%

66.667%

55.556%

 

 

 

ANSWER

저는 개인적으로 C가 더 편해서 맨날 습관적으로 C언어로 작성하게 되더라고요 ㅎㅎ

자바를 먼저 풀어야 자바 실력이 더 향상될텐뎅... 오늘은 자바로 먼저 풀어볼까요

 

[1546번 평균 문제 JAVA]

어라아ㅏㅏ 상대오차 절대오차 요거요거 익숙하지 않나요?

백준 사칙연산 문제에서 고대로 나왔었어요. 상대오차 개념이 아직 잡히지 않으신 분들은 요 글을 읽고 오시길 추천드려요. 상대오차 빼면 단순 덧셈 뺄셈 나눗셈 문제이기 때문에 어려울 게 없어요! ㅎㅎ

 

고럼 다시 문제로 돌아와서

문제가 요구하는 것은 결국 평균이네요. 가장 큰 값을 구하는 로직과, 평균을 구하는 수식을 알고 있다면 수월하게 풀 수 있는 문제입니다.

 

일단 평균을 구하는 로직을 살펴보면

각각의 점수에 새로운 계산 방식을 적용한 후 새로운 점수를 도출해 이 점수들을 가지고 평균을 구하는 방법이 있을 수 있습니다. 정말 문제가 요구하는 흐름대로 !

하지만 이렇게 수식을 정리해서 짤 수도 있겠죠?

어차피 같은 결과를 가리킬테니까요 ㅎㅎ 해당 그림은 *100만 공통으로 뺐지만

최고점 또한 모든 항에 동일하게 적용되므로 따로 빼서 묶을 수 있어요 ㅎㅎ

 

코드를 봅시당

과목의 개수가 많아질 수 있으므로 BufferedReader로 입력을 받아볼게요

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
     public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        double[] scores = new double[num];
        
        for(int i=0; i<num; i++) {
            scores[i] = Double.parseDouble(input[i]);
        }
        //오름차순 정렬
        Arrays.sort(scores);
        
        //가장 큰 값 찾기
        double max = scores[scores.length-1];
        
        //각 배열에 새로운 계산 방식을 적용해 평균 구하는 과정
        double sum=0;
        for(int i=0; i<num; i++) {
            sum += (scores[i]/max)*100;
        }
        System.out.println(sum/num);
     }
}
​

메모리: 13356KB

시간: 76ms

코드길이 : 736B

Arrays.sort() 메서드를 사용하지 않고 max 구하는 것에만 초점을 맞춤으로써

시간을 절약한 것을 확인할 수 있어요! (84ms-> 76ms)

 

[1546번 평균 문제 C]

그 다음은 C언어로 풀어볼게요.

앞의 JAVA와 알고리즘은 똑같으니

이번에는 배열마다 새로운 계산법을 적용한 뒤 평균을 구하는 방식이 아닌, 공통적인 요소들을 따로 빼서 정리한 수식으로 코드를 작성해볼게요.

#include <stdio.h>
int main()
{
    int num, score, sum=0, max=0;
    scanf("%d",&num);
    for(int i=0; i<num; i++){
        scanf("%d", &score);
        sum+=score;
        max = (max>score)? max: score;
    }
    printf("%.2f", ((float)sum/(num*max))*100);
    return 0;
}
​

메모리: 116KB

시간: 0ms

코드길이: 287B

확실히 C언어는 타입에 관련해서는 형변환이 간단해서 좀 더 편리하네요 ㅎㅎ

정리된 수식은 결국 총합만 필요하기 때문에 배열을 선언해줄 필요가 없어요! 그게 장점이라면 장점?

하지만 전 포스팅에서 설명했듯이 자바와는 다르게 상대오차때문에 자릿수를 명시해줘야 합니다.

 

[4344번 평균은 넘겠지 문제 C]

첫 문제는 JAVA로 먼저 했으니까 두 번째 문제는 C로 시작해볼까요?

여러분들도 읽으면서 느꼈겠지만 두 번째 문제 또한 수학 문제입니다. 펜으로 해당 문제를 풀 수 있으면 코딩으로 옮기는 게 어렵지 않으셨을 거예요.

 

일단, 답을 도출해볼게요

두 번째 라인의 평균을 70이라 가정하고 잡으면 -20, -20, 0, +10, +30 이므로 도합 0이되므로 70이 맞네요

그런데 70을 넘은 학생은 80, 100 두 명이예요. 다섯 명 중에 2명이 평균을 넘었네요. 즉 비율은 2/5이므로 40%, 그래서 정답이 40프로가 됐어요.

 

즉 알아야 하는 변수들을 생각해보자면, 평균점수, 넘은 사람 수, 비율계산 정도 가 핵심

평균과 비율을 계산할 줄 알면 쉽게 풀 수 있는 방법이예요.

#include <stdio.h>
int main()
{
    int testcase;
    float avg = 0;
    scanf("%d", &testcase);
    while (testcase>0)
    {
        int studentNum, count=0, sum = 0;
        scanf("%d", &studentNum);
        
        int* scores = new int[studentNum];
        for (int i = 0; i < studentNum; i++) {
            scanf("%d", &scores[i]);
            sum += scores[i];
        }
        avg = (float)sum / studentNum;
        for (int i = 0; i < studentNum; i++) {
            count += (scores[i] > avg) ? 1 : 0;
        }
        printf("%.3f%%\n", (float)count / studentNum * 100);
        testcase--;
    }
    return 0;
}​

메모리: 1176KB

시간: 0 ms

코드길이 : 534B

틀렸...ㅎㅎ 알고보니까 '%'랑 '\n'을 출력을 같이 안해줬더니 제출 후 '틀렸습니다'가 뜨더라고요..ㅎㅎㅎ

요구한 대로 출력할 수 있도록 꼼꼼이 문제를 확인하는 습관을 들입시다 ㅠㅠ

 

오늘 풀이는 여기까지?! 색다른 풀이가 있거나 더 좋은 풀이를 알고계시는 분은 알려주시면 감사합니다

오타 있으면 알려주세요!

아직 많이 부족해서 최적의 답안은 아닐 수 있으니 문제를 해결하는데 참조정도로만 봐주시면 좋겠어요 ㅎㅎ