코딩테스트 준비 - 수들의 합 5

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

• 응시 사이트 : BOJ

• 문제 : 2018.수들의_합_5

• 사용언어 : C#

• 난이도 : Easy

• 풀이시간 : 30m

• 유형 : 투 포인터

문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

예제 입력 1 복사

15

예제 출력 1 복사

4

문제 풀이 접근

이 문제는, 전형적인 투포인터 활용 문제라고 생각한다.
하지만, 초기에 내가 생각했던 아이디어에서 잘못된 생각을 2가지 정도 바로잡자면,

1. 투 포인터의 범위가 10000000이라고해서 While 문을 left 포인터를 10000000까지 돌릴 필요가 없다는 점

2. 조건에 의해서 left, right 인덱스 관리를 자세히 해야한다는 점이었다.

1번은, 내가 초기에 문제를 풀면서 While(_leftIndex < 10000000) 까지 돌리는 구문을 늦게 찾아서 포인트로 잡게되었고,

2번인 인덱스 관리를 자세히 해야한다는 점은 이런것이다.
예를들어 문제에서 주어진 N = 15 이다.
그런데, 인덱스로 계속 돌리다보면 1,2,3,4,5 는 결국 15로 결과로 출력할 카운트를 하나 올린다.
그리고 인덱스 6, 인덱스 7 을 하면 6 + 7 이되고,결국 13이다.
이 다음 인덱스로 8이 온다고해도 안맞는다.
그러나, 7+8 은 15로 결과 카운트를 하나 올려야한다. 하지만, 인덱스 6,7은 이미 지나갔고, 8에서
8 + 9 이렇게해도 정답을 찾지못한다.
고로 나는 이 문제를 leftStandard, rightStandard라는 변수를 하나 두어 기준점을 잡고, 정렬되어 있는 배열이라고 가정하기에 합당하기 때문에, 인덱스 1의 경우 1,2,3,4,5 를 돌려서 결과를 찾고,
그 다음 2인덱스 기준을 잡고 2 ~ (Right * 0.5) 의 까지 인덱스 루프를 돌리면서 값을 찾는 전략을 사용하여 인덱스 관리를 빠지는 부분없이 처리하는 방식으로 생각했다.
(이는 right 도 동일하도록 처리한다.)

작성 코드 (C#)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;

///*
// * Difficulty : Easy
// * URL : https://www.acmicpc.net/problem/2018
//  * Time : 30m
// */

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

    public class Solution
    {
        public int _n;
        public int _left;
        public int _right;
        public int _ret;

        public int[] _arr;

        public void solve()
        {
            _n = int.Parse(Console.ReadLine());
            _left = 0;
            _right = _n-1;
            _ret = 0;
            _arr = new int[_n];

            for(int i= 0; i < _n; i++)
            {
                _arr[i] = i+1;
            }

            int _leftAdd = 0;
            int _rightAdd = 0;

            int _standardLeft = 0;
            int _standardRight = 0;
            // 기준 인덱스

            while(_left < (_n * 0.5))
            {
                _standardLeft = _left;
                _standardRight = _right;
                _leftAdd = 0;
                _rightAdd = 0;

                while (_standardLeft < (_n * 0.5))
                {
                    _leftAdd += _arr[_standardLeft];

                    if (_leftAdd == _n)
                    {
                        ++_ret;
                        break;
                    }
                    else if (_leftAdd > _n)
                        break;
                    else
                        ++_standardLeft;
                }
                // Left

                while(_standardRight > (_left))
                {
                    _rightAdd += _arr[_standardRight];

                    if (_rightAdd == _n)
                    {
                        ++_ret;
                        break;
                    }
                    else if (_rightAdd > _n)
                        break;
                    else
                        --_standardRight;
                }
                // Right

                ++_left;
                --_right;
            }

            Console.WriteLine(_ret);
        }
    }
}

코드 결과