(C++) - LeetCode (easy) 263. Ugly Number

https://leetcode.com/problems/ugly-number/description/

Ugly Number - LeetCode

dp방식으로 해결했습니다.

📕 풀이방법

📔 풀이과정

ugly number를 만들기 위해 1부터 시작해서 *2, *3, *5 세 방향으로 n을 재귀형태로 만들어 나간다고 생각해봅니다.

3가지를 고려합니다.

1. 시간초과 : 재귀형태로 매번 3가지의 분기가 일어나므로 3^x형태의 call stack이 생기지 않도록 map형태의 check를 선언합니다. memoization을 사용하면 되는데, 매번 current에 대해 check해주고 정답이 나왔다면 바로 true를 반환합니다. 이미 확인했던 수라면 정답이 무조건 아니므로 바로 false를 반환하도록 합니다.

 

2. 자료형의 초과 int는 약 21억까지의 범위만 cover가능하므로 1부터 n으로 쌓아올리는 형태의 방법으로는 직전의 값이 20억이라면 *5하는 분기에 대해 100억을 확인할 수 없게 되므로 long long형태의 자료형을 이용합니다.

 

3. 재귀를 수행한 결과를 반환할 때 현재 수 current * 2, current * 3, current * 5, 중 하나라도 target인 n으로 도달하기만 해도 해당 수는 ugly number이므로 max값을 반환합니다.

---

📕 Code

📔 C++

class Solution {
public:
    map <int,int> check;
    bool getUgly(long long current, long long target) {
        if(check[current]) return false;
        check[current] = 1;
        if(current > target) return false;
        if(current == target) return true;
        return max({getUgly(current*2, target), getUgly(current*3, target), getUgly(current*5, target)});
    }

    bool isUgly(int n) {
        if(n <= 0) return false;
        return getUgly(1, n);
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.