[백준] 10단계 문제 모음
2021. 2. 4. 21:14ㆍHi/Java
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);
}
}
728x90
'Hi > Java' 카테고리의 다른 글
[백준] 12단계 문제 모음 (0) | 2021.02.15 |
---|---|
[백준] 11단계 문제 모음 (0) | 2021.02.07 |
[백준] 9단계 문제 모음 (0) | 2021.01.24 |
[백준] 8단계 문제 모음 (0) | 2021.01.18 |
[백준] 7단계 문제 모음 (0) | 2021.01.15 |