3/2기록 - 백준 2635

이전 문제가 너무 간단하게 해결이 되어서 양심상 한 문제를 더 풀어보았다. 

 

백준 2635번 수 이어가기 문제이다.

 

 

이 문제는 첫번째 수로 주어진 수에서 최대로 만들 수 있는 빼기 수를 찾아내는 것이다. 앞 수 - 뒷 수 = 그 다음 세번째 수 이런식으로 나열이 되고 몇개까지 수가 만들어질 수 있는지와 앞 수 - 뒷 수 = 음수가 나오게 되면 종료가 된다. 

 

알고리즘 생각

1. max 숫자를 출력할 list와 실제로 처리를 담당할 list를 만든다.

2. 실제 처리 리스트를 1~N까지의 반복문 안에서 형성한다.

3. N과 그 다음 수 i를 담는다.

4. 계산을 위한 first와 second 변수를 N과 i로 각각 선언한다.

5. while(true) 반복문 안에서 result 변수를 first - second로 만들고 result가 음수면 멈추고, 양수면 계속해서 실제 처리 list에 담아준다.

6. first변수를 second로, second를 result로 바꿔 주고 계속 반복문이 실행될 수 있도록 해 준다.

7. max 숫자 출력 list가 실제 처리 list보다 size가 작거나 같으면 maxnum을 실제 처리 리스트 size를 maxnum에 담아주고, max list에 실제 처리 list를 넣어준다.

8. maxnum과 max 출력 list의 인덱스를 get()으로 출력시킨다.

 

 

이렇게 해결할 수 있었다. 이 문제의 핵심은 if(max.size() <= now.size()) 이 부분인 것 같다. 이 부분에서 조건을 달아서 max list에 now list를 담아주어야 list의 최대 크기를 알 수 있기 때문이다.

 

first = second와 second = result를 해주지 않아서 처음에 잘못된 답이 계속 도출되었다. 잘 생각을 해보니 반복문 안에서 수를 계속 변형 시켜 주어야만 그 다음 값을 반복적으로 얻어낼 수 있기 때문에 반드시 필요한 작업이었는데 그 부분을 간과하고 문제를 풀었던 것 같다.

 

3/2 기록 끝!!!!!!!!