18th Koala 8주차

우왓 벌써 코알라 8주차라니!! 믿기지 않는다...₍ᐢ⑅•ω•⑅ᐢ₎ദ⸒⸒

 

이번에 코알라를 하면서 배운게 정말 많지만 빠진 주차가 몇 개 있다보니.. 그리고 내가 모르는게 정말 많은 탓에 여전히 부족함을 느끼는 것 같다..(/-᷄ ᴗ -᷅\ *)💦

그리고 C++로 하다보니 좀 더 신경써야할 부분이라던지 좀 더 복잡한 부분이 있는 것 같아서 방학때는 그냥 파이썬으로 알고리즘 공부를 해볼까한다... 파이썬으로 좀 더 공부한 후에 여유가 되면 C++로 하는게 더 나을 것 같다는 생각이 들었ㄷr ...(´,,•﹃ •,,｀)

 

 

오늘 소개할 문제는 바로 이 문제이다!! ( 𓏸˙ ᴗ˙𓏸)

 

백준 14650번 : 걷다보니 신천역 삼 (Small) 

 

 

 

백준에서 가끔 이런 컨셉문구(쓸데없는st)가 문제 설명에 들어있으면 나도 모르게 문제 읽다가 피식하는 것 같다 ㅋㅋ ( •˓◞•̀ )

 

 

여튼 이 문제는 0, 1, 2 이 3개의 숫자만을 가지고 N자리 3의배수의 개수를 출력하는 문제이다.

 

 

1. 입력 및 변수 초기화

#include <iostream>
using namespace std;

int count = 0;
int N;

 

먼저 문제에서 주어지는 자릿수 N을 입력받기 위해 전역 변수로 선언해주고, 조건을 만족하는 경우의 수를 셀 count 변수도 0으로 초기화해줬다!!

 

 

2. 재귀함수 정의

void generateNumbers(int length, int sum) {
    if (length == N) {
        if (sum % 3 == 0) {
            count++;
        }
        return;
    }

    for (int i = 0; i <= 2; i++) {
        if (length == 0 && i == 0) continue;
        generateNumbers(length + 1, sum + i);
    }
}

 

이 함수가 이 코드의 핵심이다!! 재귀적으로 숫자를 하나씩 만들어가며, 길이가 N에 도달했을 때 각 자릿수의 합이 3의 배수인지 확인해주는 구조이다!!

• length == N일 때 → 자릿수를 다 만들었을 때를 의미!!
• sum % 3 == 0이면 → 3의 배수니까 count++ 해주기
• 그 외에는 0, 1, 2 중 하나를 골라서 다음 자리로 간다
• 다만 첫 자리는 0이면 안 되기 때문에 length == 0 && i == 0 조건으로 걸러줬다

이런식으로 완전탐색처럼 모든 경우를 다 만들어보는 방식이다!! ¡¡¡( •̀ ᴗ •́ )و!!!

 

 

3. 메인함수 및 출력

int main() {
    cin >> N;
    generateNumbers(0, 0);
    cout << count << endl;
    return 0;
}

 

여기서 N 입력받고, generateNumbers(0, 0)으로 처음 재귀 호출 시작해주면 된다!! 처음엔 자리도 없고 합도 0이니까 (0, 0)으로 시작한다. 마지막으로 지금까지 센 count를 출력해주기만 하면 끝이다~! ჱ̒⸝⸝•̀֊•́⸝⸝)‪

 

처음에 이 재귀흐름을 캐치하기 어려워서 조금 더 이해를 돕기 위해 내가 그림으로 그렸던 그림이다!!

N=3인 경우에 재귀함수의 흐름이 어떻게 동작하는지 트리구조로 그려가면서 이해했다!! ໒(⊙ᴗ⊙)७✎▤

 

 

 

그리고 전체 코드는 이러하다!!

 

#include <iostream>
using namespace std;

int count = 0;
int N;

void generateNumbers(int length, int sum) {
    if (length == N) {
        if (sum % 3 == 0) {
            count++;
        }
        return;
    }

    for (int i = 0; i <= 2; i++) {
        if (length == 0 && i == 0) continue;
        generateNumbers(length + 1, sum + i);
    }
}

int main() {
    cin >> N;
    generateNumbers(0, 0);
    cout << count << endl;
    return 0;
}

 

 

 

지금까지 알고리즘 문제를 풀면서 재밌다는 생각이 든 문제가 크게 없었는데 재귀함수 파트는 유난히 재미있는 것 같다.. ◔.̮◔✧

 

생각의 흐름을 조금 바꿔야해서 그런 것 같기도 하고...!! 여튼 문제를 재귀흐름으로 바꾸어서 푸는 과정이 어렵긴하지만 생각보다 문제가 쉽게 풀린다는게 신기한 그런 파트인 것 같다!!! (~ ᵕ ̫ ᵕ)~

 

 

 

벌써 코알라 활동이 끝낫다니... 그리고 시험도 2주 남았다는게 믿기지가 않는다 ‧⁺(இㅅஇ⸝⸝ ) 시간이 왜이리 빠른지....ㅜ

 

남은기간동안 열시미해서 무사히 종강하고 방학때는 알고리즘 공부를 더 열시미 해야겟다는 생각이 든다...!!! ʸᵉᵃʰ( ᐛ✌️)~~

 

화이팅~~~~!!! ＼＼\ ٩(๑❛ワ❛๑)و //／／＼＼\ ٩(๑❛ワ❛๑)و //／／＼＼\ ٩(๑❛ワ❛๑)و //／／

 

코알라 8주차 끗~~!!!! ヾ(๑╹◡╹)ﾉ"