[백준] 10단계 문제 모음

10단계.

재귀

재귀함수를 다뤄 봅시다.

---

1

10872

팩토리얼

재귀함수를 만들어서 제출해야한다.

import java.util.Scanner;

public class Main {
	static int factory = 1;
	public static int fac(int num) {
		if(num ==0) return factory;
		else{
			factory *= num;
			return fac(num-1);			
		}
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();
		fac(x);
		System.out.println(factory);
	}

}

---

2

10870

피보나치 수 5

이 문제 또한 재귀 함수를 만들어서 푼다.

import java.util.Scanner;

public class Main {
	public static int f(int x) {
		if(x == 0) return 0;
		if(x == 1) return 1;
		return f(x-1) + f(x-2);
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		System.out.println(f(scan.nextInt()));
		scan.close();
	}

}

---

3

2447

별 찍기 - 10

이번 문제는 좀 어려웠던 것 같다.

재귀 함수를 많이 사용하지 않아봐서 어떻게 하면 돌아갈지 생각을 많이 한 문제였다.

import java.util.*;

public class Main {
    static char array[][];

    public static void star (int x, int y, int n) {
        if (n == 1){
            array[x][y] = '*';
            return;
        }
        
        int m = n/3; //하위 칸으로 줄임.
        
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                if (i==1 && j==1) continue; // 가운데는 어쩌피 빈칸이니 그냥 다음으로 넘김
                star(x+m*i, y+m*j, m); 
            }
        }
        
    }
    
    public static void main(String args[]) {
    	Scanner scan = new Scanner(System.in);
        int number = scan.nextInt();
        scan.close();
        
        array = new char[number][number];

        for (int i = 0; i < number; i++) //모든값 ' ' 로 설정.
            Arrays.fill(array[i], ' '); 

        star(0, 0, number);
        
        for (int i = 0; i < number; i++)  // 모든값 출력
            System.out.println(array[i]);
        
    }
}

---

4

11729

하노이 탑 이동 순서

크게 3단계로 만들어서 풀었다.

처음에는 아래와 같이 작성하여 시간 초과가 났다.

import java.util.Scanner;

public class Main {
	//n = 도형개수
//	a = 첫번째막대
//	b = 두번째막대
//	c = 세번째 막대
			
	public static void f(int n, int a, int b, int c) {
		if(n==1) {
			System.out.println(a + " " + c);
			return;
		}
		f(n-1, a, c, b); // n-1을 b에다 넣어야 하고 중간은 c임.
		System.out.println(a + " " + c); // n이 혼자 첫번째 막대에 있으니 세번째 막대로 옮김.
		f(n-1, b, a, c); //두번째 막대에 있는 것들을 c로 이동.
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int count =0;
		for(int i = 0; i< N; i++) {
			count = count* 2 +1;
		}
		System.out.println(count);
		f(N, 1, 2, 3);
	}

}

여기서 시간을 줄이기 위해 매번 System.out.print 하는 것을 지우고 StringBuilder을 사용하여 저장해 놓았다가 마지막에 출력하였더니 통과되었다.

import java.util.Scanner;

public class Main {
	static StringBuilder sb = new StringBuilder();
//  n = 도형개수
//	a = 첫번째막대
//	b = 두번째막대
//	c = 세번째 막대
			
	public static void f(int n, int a, int b, int c) {
		if(n==1) {
			sb.append(a + " " + c + '\n');
			return;
		}
		f(n-1, a, c, b); // n-1을 b에다 넣어야 하고 중간은 c임.
		sb.append(a + " " + c + '\n'); // n이 혼자 첫번째 막대에 있으니 세번째 막대로 옮김.
		f(n-1, b, a, c); //두번째 막대에 있는 것들을 c로 이동.
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		scan.close();
		int count =0;
		for(int i = 0; i< N; i++) {
			count = count* 2 +1;
		}
		System.out.println(count);
		f(N, 1, 2, 3);
		System.out.println(sb);
	}

}