코딩테스트 준비 - 한수

혼자서 다시푸는 코딩테스트 준비 일지 - 38

브루트포스수학

2 months ago

5 min read

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

응시 사이트 : BOJ
문제 : 1065.한수
사용언어 : C#
난이도 : 중하
풀이시간 : 미측정
유형 : 브루트포스, 수학

문제

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다.

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

예제 입력 3 복사

예제 출력 3 복사

예제 입력 4 복사

예제 출력 4 복사

예제 입력 5 복사

예제 출력 5 복사

문제 풀이 접근

이번 문제는 문제를 풀면서 새로운 아이디어를 생각해냈고, 그 아이디어가 더 쉽다고 생각해서 풀었는데 풀고나니 아쉬워서 첫번째 방법도 사용하여 총 두가지 방법으로 풀이하였다.

방법은 아래와 같다.

1. 입력으로 주어지는 값 string을 배열로 분리하여 공차를 구하고 배열의 인덱스를 모두 순회하며 공차와 같은지 끝까지 검사하는 방법

2. 공차의 공식을 사용하여 초항 a + (인덱스 * 공차) == 해당 인덱스의 값 을 구하는 방식이다.

크게 어려운 방법은 없고, 배열의 인덱스를 움직이고 비교문을 잘 작성하면 쉽게 풀 수 있다.

작성 코드 (C#) - 인덱스를 모두 순회하여 구하는 방법

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

/*
 * Difficulty : Easy ~ Middle
 * URL : https://www.acmicpc.net/problem/1065
  * Time : 
 */

// 1.배열의 완점탐색을 이용한 풀이법

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

    public class Solution
    {
        public int n;
        public int _ret;
        public int[] _arr;

        public void Solve()
        {
            n = Int32.Parse(Console.ReadLine());

            if (n < 100)
            {
                _ret = n;
            }
            else
            {
                _ret += 99; // 99 이상부터 시작
                int d = 0;
                for (int i = 100; i <= n; ++i)
                {
                    // 100 ~ n 까지 반복
                    string _input = i.ToString();
                    int _length = _input.Length;

                    int a = Convert.ToInt32(_input[0].ToString());
                    d = Convert.ToInt32(_input[1].ToString()) - Convert.ToInt32(_input[0].ToString());

                    for (int j = 1; j < _length-1; ++j)
                    {
                        int _cur = Convert.ToInt32(_input[j].ToString());
                        int _next = Convert.ToInt32(_input[j+1].ToString());

                        int _new_d = _next - _cur;

                        if (d != _new_d)
                            break;

                        if (j == (_length - 2))
                            ++_ret;
                    }
                }
            }
            print();
        }

        public void print()
        {
            Console.WriteLine(_ret);
        }
    }
}

작성 코드 (C#) - 등차수열 공식을 이용한 풀이법

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

/*
 * Difficulty : Easy ~ Middle
 * URL : https://www.acmicpc.net/problem/1065
  * Time : 
 */


//0.등차수열 공식을 이용한 풀이법

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

    public class Solution
    {
        public int n;
        public int _ret;
        public int[] _arr;

        public void Solve()
        {
            n = Int32.Parse(Console.ReadLine());

            if (n < 100)
            {
                _ret = n;
            }
            else
            {
                _ret += 99; // 99 이상부터 시작
                int d = 0;
                for (int i = 100; i <= n; ++i)
                {
                    // 100 ~ n 까지 반복
                    string _input = i.ToString();
                    int _length = _input.Length;

                    int a = Convert.ToInt32(_input[0].ToString());
                    d = Convert.ToInt32(_input[1].ToString()) - Convert.ToInt32(_input[0].ToString());

                    for (int j = 1; j < _length; ++j)
                    {
                        int _val = Convert.ToInt32(_input[j].ToString());

                        if (_val != (a + (j * d)))
                            break;

                        if (j == (_length - 1))
                            ++_ret;
                    }
                }
            }
            print();
        }

        public void print()
        {
            Console.WriteLine(_ret);
        }
    }
}