2775_부녀회장이 될테야 (JAVA)

2775번: 부녀회장이 될테야

import java.util.Scanner;

public class Main {
	static int ans = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int i=0; i<T; i++){
			ans = 0;
			int x = sc.nextInt();
			int y = sc.nextInt();

			live(x,y);
			System.out.println(ans);
		}
	}

	public static void live(int x, int y){
		if(x == 1){
			for(int i=1; i<=y; i++){
				ans += i;
			}
		}
		else{
			x -= 1;
			for(int i=1; i<=y; i++){
				live(x, i);
			}
		}
	}
}

 

[문제 예시 해석]

1) 1층 3호 입력시

     0층 1,2,3호에 모두 거주해야 함 - 1+2+3 = 6 출력

2) 2층 3호 입력시

     1층 1,2,3호에 모두 거주해야 함

         1층 1호 - 0층 1호에 거주해야 함 - 1

         1층 2호 - 0층 1,2호에 거주해야 함 - 1+2

         1층 3호 - 0층 1,2,3호에 거주해야 함 - 1+2+3

     1 + 1+2 + 1+2+3 = 10 출력

 

 

[문제 풀이 생각 과정]

1. X층 Y호 입력시 - (X-1)층 (1~Y)호 의 경우를 따져야 되는 게 반복된다 == 재귀로 구현!

2. 0층의 경우는 생각하지 않아도 된다.

    그러므로 1층의 경우를 마지막으로 생각해서 구현한다.

    1층이 입력되었을 때 해당 Y호에 대하여 ans에 더해준다. (for문)

    그외에는 live(X, 1~Y)를 이용해 재귀로 돌린다.