알고리즘 단계별로 풀어보기 : BOJ-8393(합)

문제(출처)

n이 주어졌을 때, 1부터 n까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n (1 ≤ n ≤ 10,000)이 주어진다.

출력

1부터 n까지 합을 출력한다.

예제 입력

3

예제 출력

6

내 풀이

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

public class Main {

    public static void main(String args[]) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        try {

            int num = Integer.parseInt(br.readLine().split(" ")[0]);

            int sum = 0;

            /* Test case1           

             * i부터 num까지 반복하여 sum에 합한다.

             * O(n)

             */

//          for (int i = 1; i <= num; i++) {

//              sum += i;

//          }

            

            /* Test case2

             * 홀수 짝수에 따라 규칙을 찾았다.

             * 10x(10/2)+(10/5) = 55

             * 1+2+3+4+5+6+7+8+9+10 = 55

             * O(1)

            */

            if(num%2 == 0) {

                sum = num * (num/2) +(num/2);

            }else {

                sum = num * (num/2) + num;

            }

            

            bw.write(String.valueOf(sum));

            bw.flush();

            bw.close();

        } catch (NumberFormatException e) {

            // TODO Auto-generated catch block

            e.printStackTrace();

        } catch (IOException e) {

            // TODO Auto-generated catch block

            e.printStackTrace();

        }

    }

}

내 풀이 해석

중학교 때 들어본거 같은 1부터 n까지의 합입니다.

문제의 취지는 반복문을 사용하는것이라서 반복문을 써보고 기억을 더듬어 규칙을 찾기 위해 적으면서 풀어보았습니다.

빅오 표기법으로 Test case1은 O(n)이고 Test case2는 O(1)입니다.

Test case1은 1부터 n까지 합을 반복문으로 sum에 합합니다.

Test case2는 홀수와 짝수를 구문하여 n * (n/2)을 기준으로 문제를 풀었습니다.