[BOJ] 백준 16953 A->B (JAVA)

재귀함수로도 풀린다!

📑 문제

백준 16953번 A -> B

---

🌱 아이디어

문제에서 여러 가지의 경로를 제공하면 재귀함수를 사용해서 풀 수 있다

 

전에 재귀함수를 공부하면서 가장 어려웠던 점이 재귀적 사고방식이었다, 이해하기도 전에 "여러 가지 선택지가 있으면 재귀함수도 고려해 보자"라는 생각을 박아 놨던 것 같다.

 

재귀함수 흐름도

처음 노드에서 조건 1을 실행하고 조건 1-1에서 결과값이 B가 될 수 없다면 return 하고 전 노드로 되돌아가 조건 1-2를 선택하게 된다.

 

본문에서 "가능한 연산은 두 가지" 라고 제시했다. 즉 우리는 "2*A"를 선택할 때와 "A*10 +1"을 선택할 때를 재귀적으로 호출하면 된다!

두 가지 경우를 만들어 놓는다면 나머지는 컴퓨터가 알아서 해줄 것이다.

---

 🌱 코드 및 풀이

sum = 10억 일 때 조건 2를 연산하면 정수형 범위를 벗어나게 된다 "long"형으로 선언해 주자.

 

위에서 적은 것 말고는 그다지 어려운 것 없다. 다만 재귀가 익숙하지 않다면 지금 당장 공책피고 손으로 노드를 따라 그려보자!

필자는 아직도 그런다

---

🌱 느낀 점

속도도 빠르다!

재귀함수를 사용할 때 연산하는 횟수를 신경 써야 한다, 시간초과가 발생하기 때문이다;;

따라서 위 문제의 조건 2번이 없었다면 10억이라는 최대 값이 들어왔을 때 분명 시간초과를 했을 것이다.

처음 재귀를 배울 때 가장 막막했던 것 같은데 지금은 어느 정도 재귀를 활용할 수 있다는 것에 다행이라고 느낀다 ㅠ