sw 2005. 파스칼의 삼각형 (자바)
[문제]
크기가 N인 파스칼의 삼각형을 만들어야 한다.
파스칼의 삼각형이란 아래와 같은 규칙을 따른다.
1. 첫 번째 줄은 항상 숫자 1이다.
2. 두 번째 줄부터 각 숫자들은 자신의 왼쪽과 오른쪽 위의 숫자의 합으로 구성된다.
N이 4일 경우, N을 입력 받아 크기 N인 파스칼의 삼각형을 출력하는 프로그램을 작성하시오.
[제약 사항]
파스칼의 삼각형의 크기 N은 1 이상 10 이하의 정수이다. (1 ≤ N ≤ 10)
[입력]
가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스에는 N이 주어진다.
[출력]
각 줄은 '#t'로 시작하고, 다음 줄부터 파스칼의 삼각형을 출력한다.
삼각형 각 줄의 처음 숫자가 나오기 전까지의 빈 칸은 생략하고 숫자들 사이에는 한 칸의 빈칸을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)
[문제 해결 과정]
테스트 케이스의 갯수 T를 입력받고 걔만큼 반복한다.
반복문 안 에서 N을 입력받는다. 크기 N인 파스칼의 삼각형을 출력한다.
그럼 줄을 N개를 출력해야 한다.
1번째 줄은 1
2번째 줄은 1 1
3번째 줄은 1 2 1
4번째 줄은 1 3 3 1
5번째 줄은 1 4 6 4 1
6번째 줄은 1 5 10 10 5 1
이렇게 된다. 각 줄은 1로 시작하고, 이전 줄의 숫자들을 알고 있어야함!!
만약 m번째 줄에 들어가는 값을 계산한다면,
m번째 줄의 0번째 인덱스 값 : 1
m번째 줄의 1번째 인덱스 값 : m-1번째 줄의 0번째 + 1번째 인덱스 값
m번째 줄의 2번째 인덱스 값 : m-1번째 줄의 1번째 + 2번째 인덱스 값
m번째 줄의 3번째 인덱스 값 : m-1번째 줄의 2번째 + 3번째 인덱스 값
.
.
.
이런 식으로 만들었다가 마지막 m-1번째 인덱스는? 무조건 1임.
이렇게 하면된다. 그럼 지금 이전 줄을 기억하고 있어야 현재 줄을 만들 수 있으니까 배열이 무조건 필요할 것 같고.. N값이 주어지면 배열을 N개 만들어도 되긴 하지만 이전 줄과 현재 줄만 담으면 되니까 배열은 두개만 필요할 것 같기도 하고?
아니면 2차원 배열을 써야되나?? 그러면 맨 마지막 줄의 숫자가 들어가려면 두번째 칸?이 많아야 되는데 그럼 맨 윗줄에서는 숫자 몇개 채우고 남는 칸은 그냥 비워둬도 되는건가??
그럼 만약 N이 6이면 줄은 총 6줄이고 가장 마지막 줄에 숫자가 6개 적힐 것이므로
int[6][6] 이렇게 2차원 배열을 생성하면 되겠다!!
테스트 케이스 숫자 T를 받아들이고, 걔만큼 for문을 돌린다.
반복문 안에서 N을 받아들인다. 파스칼의 삼각형을 N줄 만들어야 하고 가장 마지막 줄에는 숫자가 N개 들어가야 한다. 그래서 int[][] triangle = new int[N][N] 이렇게 2차원 배열을 만들어준다.
int[0][0] 는 무조건 1이다.
int[1][0] 도 1, int[1][1] 도 무조건 1이다. 즉 int[~][0]과 int[~][~]는 무조건 1이다.
N-1번째 인덱스의 줄의 m번째 인덱스 값은 N-2번째 인덱스 줄의 m-1번째 인덱스 값과 m번째 인덱스 값을 더한 것과 같다.
이런 식으로 값을 넣어준 다음 출력도 반복문 돌려서 출력하자!!
출력을 어떻게 하지??? 한 줄씩 출력하고 엔터치기….
이차원 배열 말고 그냥 한 줄 씩 배열을 만들어볼까??
문제 패스 49분 50초 걸림
[제일 처음으로 패스한 코드]
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i = 0; i < T; i++) {
int N = sc.nextInt();
int[][] triangle = new int[N][N];
System.out.println("#"+ (i+1) );
for(int j = 0 ; j < N ; j++) {
triangle[j][0] = 1;
triangle[j][j] = 1;
// 맨 윗줄 숫자는 무조건 1
// 두번째 줄 숫자도 1 1
// 몇번째 줄이던 맨 앞과 맨 뒤는 무조건 1
// 이제부턴 2번째 인덱스 줄부터 생각 (j번째 인덱스 줄이라고 생각)
for(int l = 1; l <= j-1; l++) {
triangle[j][l] = triangle[j-1][l-1] + triangle[j-1][l];
// j번째 줄의 l번째 값은 j-1번째 줄의 l-1번째값과 l번째 값의 합과 같음.
}
}
for(int m = 0 ; m < N ; m++) {
// m번째 줄이면 m+1개가 출력되야함
for(int n = 0 ; n < m+1 ; n++) {
System.out.printf("%d ",triangle[m][n]);
}
System.out.println("");
}
}
}
}[문제 풀고 난 후]
대체로 2차원 배열로 많이 풀었음. 다른 사람들 풀이 보면서 반복문 최대한 줄임!!
[출력할 때 for문 하나 줄이고 원래 for문에 합친 코드]
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i = 0; i < T; i++) {
int N = sc.nextInt();
int[][] triangle = new int[N][N];
// 가로 N줄 세로 N줄인 정사각형 이차원 배열 만들기
System.out.println("#"+ (i+1) );
// 몇번째 테스트 케이스인지 쓰기
for(int j = 0 ; j < N ; j++) {
triangle[j][0] = 1;
triangle[j][j] = 1;
// 맨 윗줄 숫자는 무조건 1
// 두번째 줄 숫자도 1 1
// 몇번째 줄이던 맨 앞과 맨 뒤는 무조건 1
// 이제부턴 2번째 인덱스 줄부터 생각 (j번째 인덱스 줄이라고 생각)
for(int l = 1; l <= j-1; l++) {
triangle[j][l] = triangle[j-1][l-1] + triangle[j-1][l];
// j번째 줄의 l번째 값은 j-1번째 줄의 l-1번째값과 l번째 값의 합과 같음.
}
for(int n = 0 ; n < j+1 ; n++) {
System.out.printf("%d ",triangle[j][n]);
// 숫자 적고 오른쪽 한칸 띄어쓰기
}
System.out.println("");
// 엔터 한번
}
}
}
}별로 드라마틱하게 코드가 줄어들진 않았다.
[맨 윗줄과 두번째 줄도 for문 안에 같이 넣어서 계산하기]
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i = 0; i < T; i++) {
int N = sc.nextInt();
int[][] triangle = new int[N][N];
// 가로 N줄 세로 N줄인 정사각형 이차원 배열 만들기
System.out.println("#"+ (i+1) );
// 몇번째 테스트 케이스인지 쓰기
for(int j = 0 ; j < N ; j++) {
// j번째 줄에서..
for(int l = 0; l <= j; l++) {
// j번째 줄에는 숫자 j+1개 있음
if(j == l || l == 0) {
triangle[j][l] = 1;
// 맨 윗줄 숫자는 무조건 1
// 두번째 줄 숫자도 1 1
// 몇번째 줄이던 맨 앞과 맨 뒤는 무조건 1
} else {
triangle[j][l] = triangle[j-1][l-1] + triangle[j-1][l];
// j번째 줄의 l번째 값은 j-1번째 줄의 l-1번째값과 l번째 값의 합과 같음.
}
System.out.printf("%d ",triangle[j][l]);
// 숫자 적고 오른쪽 한칸 띄어쓰기
}
System.out.println("");
// 엔터 한번
}
}
}
}이게 이차원 배열에 파스칼의 삼각형을 넣으면 맨 아랫줄은 모든 칸이 다 차는데 반해 윗줄로 올라갈수록 배열 뒷칸들은 비어있게 되니 이차원 배열로 하는게 맞나.. 싶었는데 다른 사람들도 다 이차원 배열로 풀었다. 처음에는 한줄 한줄 매번 배열을 새로 만들까 생각했는데 그것도 별로고.. 배열 두개만 만들어놓고 이전 배열이랑 (지금 배열의 값을 계산하는데 이전 배열이 필요하니까) 지금 배열만 담고 계속계속 배열 비우고 새로넣고 하면서 할까 했는데 그것도 비슷하게 칸이 낭비될것 같고.. 어 어쨌든 그냥 이차원 배열이 그나마 가장 나은것같다!!
정수 넣을 이차원 배열을 만들어놓고 아무값도 안 넣으면 기본값으로는 0이 들어간다!! String 들어갈 배열에서 아무것도 안 넣으면 기본값은 nul이다.
음 어쨌든 이 파스칼의 삼각형 문제는 2차원 배열로 푸는게 가장 나은 듯 하다.
[나의 깜찍한 필기]
