[BOJ] 백준 1568 새

출처: https://www.acmicpc.net/problem/1568

Approach

주어지는 N의 최대값 10^9 이기 때문에

for문으로 연산해도 1초만에 처리할 수 있다.

▶ [알고리즘] 알고리즘 문제에서 시간 복잡도는 어떻게 하는걸까? 

▶ [알고리즘] 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기 

 

문제 처리하는 로직상 +1씩 새를 날리는것이 아닌

등차수열적으로 날리기 때문에 TLE 발생하지 않는다.

 

숫자 K로 새를 날려보낼 때,

현재 남아있는 새보다 많지 않도록 유의한다.

 

C++

#include <iostream>
using namespace std;

int N, ans, bird;

int main(void)
{
    // freopen("input.txt", "r", stdin);
    cin >> N;

    ans = bird = 1;
    while (1)
    {
        if (N - bird >= 0) // 남은 있는 만큼만 제외할 수 있도록 처리
        {
            N -= bird;
        }
        else // 처리하지 못한 경우, 다시 1부터
        {
            bird = 1;
            N -= bird;
        }

        if (N == 0)
        {
            break;
        }

        bird++;
        ans++;
    }

    printf("%d\n", ans);
}

 

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = Integer.parseInt(sc.next());
        
        int cnt = 0;
        int outBird = 0;
        while(true) {
            
            // 불러지는 노래 바꿔말해 날라가는 새의 개수
            outBird++;
            
            // 만약 현재 남아 있는 새의 수보다 클 경우 1부터 다시 시작한다.
            if(N < outBird) {
                outBird = 1;
            }
            
            // 노래를 불러 해당하는 숫자 만큼 새를 날린다.
            N = N-outBird;
            
            // 시간을 counting한다.
            cnt++;
            
            // 만약 모든 새가 날라갔다면 시간을 출력하고 종료
            if(N <= 0) {
                System.out.println(cnt);
                return;
            }
        }
    }
}