[프로그래머스] 23 : 피보나치 수 | 카펫

목차💻

▸ 피보나치 수
▸ 카펫

---

💡피보나치 수 : Lv.2

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 연습문제 > 피보나치 수

▼ 내 풀이

• 배열을 활용하여 피보나치 수를 저장한다.

[오답 코드]
class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] arr = new int[n+1];
        
        arr[0] = 0;
        arr[1] = 1;
        
        for(int i = 2; i <= n; i++){
            arr[i] = arr[i-1] + arr[i-2];
        }
        
        answer = arr[n]%1234567;
        return answer;
    }
}

• 코드를 돌려보니 절반의 케이스에서 실패가 떴다.
• 찾아보니 int 타입과 long 타입을 벗어나는 경우가 생기기 때문이다.
• 따라서, 배열에 피보나치수를 1234567로 나눈 나머지를 우선 저장한다.
• 정답을 반환할 때 한번 더 %1234567 적용한다.
• 이렇게 하면 오버플로우를 피할 수 있다.

[수정 코드]
class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] arr = new int[n+1];
        
        arr[0] = 0;
        arr[1] = 1;
        
        for(int i = 2; i <= n; i++){
            arr[i] = (arr[i-1]%1234567 + arr[i-2]%1234567);
        }
        
        answer = arr[n]%1234567;
        return answer;
    }
}

▼ 알게된 점

• (A+B) % C = ((A%C) + (B%C)) % C

---

💡 카펫 : Lv.2

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 완전탐색 > 카펫

▼ 내 풀이

• 우선, yellow의 약수 중 가로길이는 세로길이보다 같거나 길다고 했기 때문에 yellow의 약수의 조합 중 큰 수를 가로로 한다.
• 예를 들어, yellow가 24일 때, 약수는 1, 2, 3, 4, 6, 8, 12, 24 이고 가로가 될 수는 6, 8, 12, 24 이다.
• 여기서 이 가로를 통해 (가로+2)*2 + (세로)*2 = brown이 되는 수를 찾는다. 예시에서는 6이 된다.
• 따라서 yellow는 6*4가 되므로 전체 카펫의 크기는 8*6이 된다.

import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(int brown, int yellow) {
        
        List<Integer> list = new ArrayList<>();
        
        for(int i = 1; i <= yellow; i++){
            if(yellow%i == 0){
                list.add(i);
            }
        }
        
        int[] answer = new int[2];
        
        for(int i = list.size()/2; i < list.size(); i++){
            int width = list.get(i);
            int length = yellow/width;
            if(((width+2)*2 + length*2)==brown){
                answer[0] = width+2;
                answer[1] = length+2;
            }
        }
        return answer;
    }
}