코딩테스트 준비 - 수 이어가기

다시푸는 코딩 테스트 준비 일지

응시 사이트 : BOJ
문제 : 2635.수 이어가기
사용언어 : C#
난이도 : 중하
풀이시간 : 27m
유형 : 브루트포스

문제

다음과 같은 규칙에 따라 수들을 만들려고 한다.

첫 번째 수로 양의 정수가 주어진다.
두 번째 수는 양의 정수 중에서 하나를 선택한다.
세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

입력

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

출력

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

예제 입력 1 복사

예제 출력 1 복사

8
100 62 38 24 14 10 4 6

문제 풀이 접근

이 문제를 처음봤을 때, 내가 떠오른 아이디어는 피보나치 였다.
앞의 수가 뒤의 두 수에 더해지는 것이 원리인 알고리즘이다.

단, 이 문제에서는 내가 n 이라는 수를 선택할 수 있고, 그 선택을 하여 만들어낸 수열이 가장 긴 것을 출력하라는게 요구 사항이다.

문제의 예를 들어 100을 입력한다고 하자.
100 의 그 다음 수는 내가 아무거나 선택할 수 있지만 정답 기준으로 보면 62가 선택된 이후
100 <= 62 + 38
62 <= 38 + 24
38 <= 24 + 14
24 <= 14 + 10
14 <= 10 + 4
10 <= 4 + 6
4 <= 6 + (-2)

음수 일때는 제한 사항으로 두었다.
위 제시한 문제를 보면 딱 생각나는 형태가 피보나치였다. fibbo(n) + fibbo(n+1) 와 같은 형태 말이다.

이제 위에 제시한 그대로 코드에 입력해주면 쉽게 풀리게 된다.

정답 작성 코드 (C#)

using System;
using System.Collections.Generic;
using static CodingTestProj.Program;

/*
 * Difficulty : Easy ~ Middle
 * URL : https://www.acmicpc.net/problem/2635
  * Time : 27m
 */


namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            var ss = new Solution();
            ss.Solve();

        }
    }

    public class Solution
    {
        int input;

        List<int>[] list;

        List<int> ret = new List<int>();

        int count = 0;

        public void Solve()
        {
            input = Int32.Parse(Console.ReadLine());
            list = new List<int>[input + 1];

            for(int i = 0; i < input +1; ++i)
                list[i] = new List<int>();

            for(int i = 1; i <= input; ++i)
            {
                var retList = list[i];
                retList.Add(input);
                fibbo(input, i, ref retList);
            }

            print();
        }
        
        public int fibbo(int o, int n, ref List<int> list)
        {
            if (n < 0)
            {
                if(count < list.Count)
                {
                    count = list.Count;
                    ret = list;
                }
                return 0;
            }
            else
            {
                list.Add(n);
            }
            

            return fibbo(n, o - n, ref list);
        }

        public void print()
        {
            Console.WriteLine(ret.Count);

            for (int i = 0; i < ret.Count; ++i)
                Console.Write(ret[i]+" ");
        }
    }
}

코드 결과

문제

다음과 같은 규칙에 따라 수들을 만들려고 한다.

첫 번째 수로 양의 정수가 주어진다.

두 번째 수는 양의 정수 중에서 하나를 선택한다.

세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.

음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

문제 풀이 접근

이 문제를 처음봤을 때, 내가 떠오른 아이디어는 피보나치 였다.
앞의 수가 뒤의 두 수에 더해지는 것이 원리인 알고리즘이다.

정답 작성 코드 (C#)

using System; using System.Collections.Generic; using static CodingTestProj.Program; /* * Difficulty : Easy ~ Middle * URL : https://www.acmicpc.net/problem/2635 * Time : 27m */ namespace CodingTestProj { internal class Program { static void Main(string[] args) { var ss = new Solution(); ss.Solve(); } } public class Solution { int input; List<int>[] list; List<int> ret = new List<int>(); int count = 0; public void Solve() { input = Int32.Parse(Console.ReadLine()); list = new List<int>[input + 1]; for(int i = 0; i < input +1; ++i) list[i] = new List<int>(); for(int i = 1; i <= input; ++i) { var retList = list[i]; retList.Add(input); fibbo(input, i, ref retList); } print(); } public int fibbo(int o, int n, ref List<int> list) { if (n < 0) { if(count < list.Count) { count = list.Count; ret = list; } return 0; } else { list.Add(n); } return fibbo(n, o - n, ref list); } public void print() { Console.WriteLine(ret.Count); for (int i = 0; i < ret.Count; ++i) Console.Write(ret[i]+" "); } } }

코드 결과