[코드카타] 재귀함수로 문제 풀다가 실수한 것 정리 ㅠㅠ

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

프로그래머스

요 문제를 풀면서 재귀 함수 만들어 풀려고 하면서 실수한 것을 정리해보자.

 

1차 시도

using namespace std;
int reward = 0;

void addReward(int a, int b, int n) {
    if (n < a) { return; }
    else if (n == a) { reward += b; return; }
    
    reward += (n-n%a)*b/a;
    return addReward(a, b, n%a + (n-n%a)*b/a);
}

int solution(int a, int b, int n) {
    addReward(a, b, n);
    return reward;
}

 

 

첫번째 문제점: 재귀 함수 쓰는 방식에 대한 얕은 이해도...ㅠㅠ

전역 변수를 사용하는 게 약간 재귀 함수를 쓰는 의미?를 흐린다... reward 값을 누적하는 건데 그걸 재귀 호출에 쓸 생각을 못했다.

 

2차 시도

using namespace std;

int addReward(int a, int b, int n) {
    if (n < a) { return 0; }
    else if (n == a) { return b; }
    
    int reward = (n-n%a)*b/a;
    return reward + addReward(a, b, n%a + reward);
}

int solution(int a, int b, int n) {
    int reward = addReward(a, b, n);
    return reward;
}

 

두번째 문제점: (특히 나눗셈이 포함된) 복잡한 연산은 순서에 따라 자료형 등 주의 필요...

1. (n - n%a) / a 는 결국 int 형일 때 n / a 랑 똑같잖아 바보야!!!!!

2. 나눗셈을 먼저하고 거기에 b를 곱해야 ratio 를 정확히 적용 가능하다.

 

결과

 

using namespace std;

int addReward(int a, int b, int n) {
    if (n < a) { return 0; }
    else if (n == a) { return b; }
    
    int reward = (n/a) * b;
    return reward + addReward(a, b, n%a + reward);
}

int solution(int a, int b, int n) {
    int reward = addReward(a, b, n);
    return reward;
}

보기에 좋은 떡이 먹기에도 좋은 것 같다.

연산의 단계를 나누어서 simplify 하고 적절한 이름을 붙이면, 연산 및 재귀 함수 호출의 순서나 단계를 이해하며 코드를 작성하기에 더 수월한 것 같다.