[백준] 2775. 부녀회장이 될테야 (브론즈1, Java)

문제

풀이

1번째 시도: 실패

예시 문제는 다 맞았다...! 하지만 틀렸다고 나온다...

import java.util.*;

public class Main {
    private static int[][] aptFill(int[][] apt, int downk, int n) {
        if(apt[downk][n] == 0) {
            apt = aptFill(apt, downk-1, n);
        }
        
        for(int i=2; i<=n; i++) {
            for(int j=1; j<=i; j++) {
                apt[downk+1][i] += apt[downk][j];
            }
        }
        
        return apt;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        int[][] apt = new int[15][15];
        for(int i=0; i<15; i++) {
            apt[0][i] = i;
            apt[i][1] = 1;
        }
        
        for(int i=0; i < tc; i++) {
            int k = sc.nextInt(); // 층
            int n = sc.nextInt(); // 호
            
            if(apt[k][n] == 0) {
                apt = aptFill(apt, k-1, n);
            }
            
            System.out.println(apt[k][n]);
        }
    }
    
}

 

질문 게시물에 올린 답변에 반례를 알려주셨다. 덕분에 문제인 부분을 찾았다.

1번 TC에서 답을 출력하고

2번 TC에서 답을 구하는 과정에서 1번 TC에 수행했던 'apt[downk + 1][i]' 값에 apt[downk][i] 값을 계속 더했기때문이었다...

 

 

2번째 시도: 성공

문제인 부분을 아래와 같이 수정했다.

이미 존재할 경우에는 값을 건들지 않고 존재하지 않는 경우에만 값 설정을 하도록 구현했다!

처음에는 아예 세팅 후에 값을 출력해야하나 싶었지만, 필요한 값만큼만 계산하고 싶었다. 따라서 조건문 추가로 구현 완료 ㅎㅎ 뿌뜻하다!

 

 

 

 

최종 코드

import java.util.*;

public class Main {
    private static int[][] aptFill(int[][] apt, int downk, int n) {
        if(apt[downk][n] == 0) {
            apt = aptFill(apt, downk-1, n);
        }
        
        for (int i = 2; i <= n; i++) {
            if (apt[downk + 1][i] == 0) {
                for (int j = 1; j <= i; j++) {
                    apt[downk + 1][i] += apt[downk][j];
                }
            }
        }
        
        return apt;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        int[][] apt = new int[15][15];
        for(int i=0; i<15; i++) {
            apt[0][i] = i;
            apt[i][1] = 1;
        }
        
        for(int i=0; i < tc; i++) {
            int k = sc.nextInt(); // 층
            int n = sc.nextInt(); // 호
            
            if(apt[k][n] == 0) {
                apt = aptFill(apt, k-1, n);
            }
            
            System.out.println(apt[k][n]);
        }
    }
    
}

 

 

백준 문제

https://www.acmicpc.net/problem/2775