[BOJ_16953] A -> B

 

📌 문제 링크: https://www.acmicpc.net/problem/16953

16953번: A → B

 

❌ 내 풀이(Failure) :

메모리 초과로 실패

 

✅ 내 풀이(Success) :

 

🧐 Review:

 BFS를 이용해서 풀이를 구현하는 것은 어렵지 않았고, 주어진 테스트 케이스도 모두 통과해서 제출했지만 메모리 초과가 발생했다. 그래서 문제를 다시 읽어보니 입력 값으로 주어지는 a와 b의 값이 최대 10억으로 정말 큰 수였다. 그래서 b의 값을 이용해 배열을 선언한다면 메모리 초과가 발생할 수밖에 없었다. 그래도 혹시 모르니까 기존의 풀이에서 배열을 1개만 사용하도록 변경했지만 여전히 메모리 초과가 발생했다. 따라서 b의 값으로 미리 배열을 선언하면 메모리 초과가 발생하는 결과로 이어지기에 배열을 선언하지 않고 문제를 해결하는 방법을 생각했고, 위의 두 번째 풀이로 이 문제를 통과할 수 있었다.

 

🚩 Idea:

 - 문제를 봤을 때 이와 유사한 문제 풀이 경험으로 BFS를 이용하면 되겠다는 생각이 들었다.