[백준, 자바, 13909번] 창문 닫기

풀이

• 해당 문제는 일반적인 방법으로 해결할 수 없다는 걸 알게 됨..
• 이유는 배열을 N개 만큼 만들게 되면 메모리 초과가 발생함.
• 그래서 다른 방법이 없을까 하나씩 찾아보니
• 그냥 어떤 분기에서 변화가 있는지 Set에 넣어보면서 찾다보니
• 계차수열 규칙을 발견

// 1    -> 1
// 2    -> 1 0
// 3    -> 1 0 0
// 4    -> 1 0 0 1
// 5    -> 1 0 0 1 0
// 6    -> 1 0 0 1 0 0
// 7    -> 1 0 0 1 0 0 0
// 8    -> 1 0 0 1 0 0 0 0
// 9    -> 1 0 0 1 0 0 0 0 1
// 10   -> 1 0 0 1 0 0 0 0 1 0
// 11   -> 1 0 0 1 0 0 0 0 1 0 0
// 12   -> 1 0 0 1 0 0 0 0 1 0 0 0
// 13   -> 1 0 0 1 0 0 0 0 1 0 0 0 0
// 14   -> 1 0 0 1 0 0 0 0 1 0 0 0 0 0
// 15   -> 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
// 16   -> 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1


// 1 4 9 16
//  3 5 7  9

• 그래서 아래와 같이 코드를 작성하여 해결.

// 성공

import java.util.*;

public class _13909 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int result = 1;
        int st = 3;
        int now = 1;
        while (true) {
            if (N>=now+st) {
                now+=st;
                result++;
                st+=2;
            } else break;

        }
        System.out.println(result);
    }
}