[랜덤 마라톤] The Big Dance(6012)

1. 문제 풀이 아이디어

• 재귀를 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        System.out.println(solve(1, n));
        bufferedReader.close();
    }

    private static int solve(int a, int b) {
        if (b - a == 1)
            return a * b;
        if (a == b)
            return 0;
        return solve(a, (a + b) / 2) + solve((a + b) / 2 + 1, b);
    }
}

3. 정리

• 재귀 함수 solve를 구현하여 문제를 해결한다.

• b-a가 1이면 a*b를 반환하며, a와 b가 같으면 0을 반환한다.

• 범위를 a부터 (a+b)/2까지와 (a+b)/2+1부터 b까지로 나누어 재귀적으로 호출한 결과를 더한다.