[boj][c++] 1759 암호만들기, 14501 퇴사

1759 암호 만들기

재귀함수를 사용해서 풀었다. 한달 전까지도 재귀함수==DFS 라는 생각을 갖고 있었는데 부정확한 말이라는게 이제서야 와닿는다. 재귀함수라는 큰 틀 안에 DFS가 포함된다.

L개의 알파벳 중 C개를 뽑아서 사용가능한 암호인지 판단해야 한다. C개의 알파엣에 모음이 한글자 이상, 자음이 두글자 이상 포함되면 사용가능한 암호이다.

인자를 index 하나만 받았다. 코드를 작성할 때 다른 인자를 받을 필요를 못 느꼈는데 지금 생각해보니 temp 를 전역변수가 아니라 재귀함수 인자로 받아와도 괜찮았을 것 같다.

• 정답을 찾은 경우
  • index == C 일 때
  • temp >= 1 && C - temp >= 2 일 때
  • 원하는 형식으로 출력
• 정답을 찾지 못한 경우
  • 이번 코드는 정답을 찾지 못한 경우를 정답을 찾은 경우 안에 포함시켰다.
• 다음 경우
  • 현재 인덱스 + 1

#include <iostream>
#include <algorithm>
using namespace std;

int l, c, a, temp;
char depth[15];
char arr[15];
bool check[15];

void go(int idx)
{
    if (idx == c)
    {
        if (temp >= 1 && c - temp >= 2)
        {
            for (int i = 0; i < c; i++)
                cout << depth[i];
            cout << '\n';
        }
        return;
    }
    for (int i = 0; i < l; i++)
    {
        if (check[i] == true)
            continue;
        if (depth[idx - 1] > arr[i])
            continue;
        if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
            temp++;
        check[i] = true;
        depth[idx] = arr[i];
        go(idx + 1);
        check[i] = false;
        if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
            temp--;
    }
}

int main()
{
    cin >> c >> l;
    for (int i = 0; i < l; i++)
        cin >> arr[i];
    sort(arr, arr + l);
    go(0);
}

14501 퇴사

난이도는 위의 문제보다 낮은데 체감상 더 어려웠다.
마찬가지로 재귀함수를 사용해서 풀었다.

• 정답을 찾은 경우 day == n
• 정답을 찾지 못한 경우 day > n
• 다음 경우
  • 현재 날짜의 상담을 포함하는 경우
  • 현재 날짜의 상담을 포함하지 않는 경우

이렇게 틀을 짜서 풀면 된다. 위의 문제는 인자 활용을 못해서 아쉬웠으나 이번 경우는 문제에서 요구하는게 조금 달라서 전역변수를 사용해야 했다.

문제를 풀면서 고민됐던 부분은

- 다음 경우
  - 현재 날짜의 상담을 포함하는 경우
  - 현재 날짜의 상담을 포함하지 않는 경우

이 부분인데, 분기를 나눠야 한다는 생각은 했으나 식으로 어떻게 표현할지에서 막혔었다. 로직을 제대로 짜놓고도 답에 접근하지 못했다.

처음에는 재귀함수 내에 다음 경우에 반복문을 이용하려고 했었는데, 짜다보니 중복되는 값이 생긴다는 문제를 찾게 됐다.

생각해보니 반복문을 쓸 필요가 없는 문제였다. 한번 지나간 값을 다시 쓸 일도 없고, 분기를 나누는데 오히려 반복문이 방해됐다. 그래서 반복문을 삭제하고 재귀함수를 두번 호출하는 것으로 문제를 해결했다.

#include <iostream>
using namespace std;

int n, ans;
int arr[16];
// time
int t[16];
// price
int p[16];

void go(int day, int sum)
{
    if (day == n)
    {
        ans = max(ans, sum);
        return;
    }
    if (day > n)
        return ;
    go(day + t[day], sum + p[day]);
    go(day + 1, sum);
    return ;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> t[i] >> p[i];
    }
    go(0, 0);
    cout << ans << '\n';
    return 0;
}