[Codeforces][Round #EDU111][Div.2] A : Find The Array (C++)

https://codeforces.com/contest/1550/problem/A

Problem - A - Codeforces

 

 

[난이도] Div.2
[유형] Greedy

[풀이]

배열을 전부 만들어봐야 하는지, DP로 풀어야하는지 등등 여러 삽질을 하다가
A번 문제인데도 컨테스트중에 풀지 못한 문제입니다. ㅠㅠ

tutorial을 보니 접근을 완전히 잘못 한것을 깨달았습니다.

n이 배열의 모든 원소의 합이라고 할때
n==1 -> [1] : 길이1
n==4 -> [1,3] : 길이2
n==9 -> [1,3,5] : 길이3
n==16 -> [1,3,5,7] : 길이4
...

위와같이 n이 1,2,3,4..의 제곱수이면 최소 배열의 길이가 1씩 늘어남을 알 수 있습니다. (2씩 큰수를 추가하면 되므로)

1 2개
4 3개
9 4개
각 배열의 마지막수를 1씩 감소시켜서 배열을 만들어보면
위와같이 n일때 최소 배열의 길이를 찾을 수 있습니다.

예를 들어 n==10일때를 구해본다면
[1,3,5,7]을 [1,3,5,1]로 바꿔주는 식으로 마지막 수를 1씩 줄여보면 모든 n에 대해서 구할 수 있습니다.

https://github.com/has2/Problem-Solving/blob/master/codeforces/RoundEDU111-Div.2/A.cpp