https://school.programmers.co.kr/learn/courses/30/lessons/120871

📔문제

3x 마을 사람들은 3을 저주의 숫자라고 생각하기 때문에 3의 배수와 숫자 3을 사용하지 않습니다. 3x 마을 사람들의 숫자는 다음과 같습니다.

10진법	3x 마을에서 쓰는 숫자	10진법	3x 마을에서 쓰는 숫자
1	1	6	8
2	2	7	10
3	4	8	11
4	5	9	14
5	7	10	16

정수 n이 매개변수로 주어질 때, n을 3x 마을에서 사용하는 숫자로 바꿔 return하도록 solution 함수를 완성해주세요.

---

🚫제한사항

1 ≤ n ≤ 100

---

📝입출력 예

n	result
15	25
40	76

---

📝입출력 예 설명

입출력 예 #1

15를 3x 마을의 숫자로 변환하면 25입니다.

---

입출력 예 #2

40을 3x 마을의 숫자로 변환하면 76입니다.

---

🧮알고리즘 분류

• dp
• 수학
• 조건문
• 배열

---

📃소스 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        answer=isnum(n);     
        return answer;
    }
    public int isnum(int n){
        int num;
        if(n==1){
            return 1;
        }
        else{
            num=isnum(n-1)+1;
        }
        while(num%3==0 || String.valueOf(num).contains("3")){
            num=num+1;
        }
        
        return num;
    }
    
}

---

📰출력 결과

---

📂고찰

한 두시간 동안 고민했던 것 같다..

그래서 결정한 건 또 등장한 재귀함수
3의 배수이거나 3이 포함되어있으면 num을 더해주고 그걸 return한다
만약 n이 3일 때, num의값은 isnum(2)+1이 되어 원래는 3인데 밑에 while문에걸려서 num은 4로 나온다.

DP를 활용했으면 좋았을 것 같다..ㅎ 값을 저장해서 불러올걸 싶기도 하다!

❔Dynamic Programming(동적 계획법, DP)

https://hongjw1938.tistory.com/47

DP는 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다.

즉, 큰 문제를 작은 문제로 쪼개서 그 답을 저장하고 재활용하는 것이다.

DP를 사용하기 위해서는,

겹치는 부분 문제(동일한 작은 문제들이 반복적으로 나타나는 경우)이고,
최적 부분 구조
(부분 문제의 최적 결과 값을 활용해 전체의 문제 최적 결과를 낼 수 있는 경우)이어야 한다.

그리고, 변수 값에 따른 결과를 저장할 배열을 미리 만들고, 그 결과를 나올 때 마다 배열 내에 저장하고, 그 저장된 값을 재활용 하는 것이다.