https://www.acmicpc.net/problem/1789
문제
> 서로 다른 N개의 자연수의 합이 S라고 한다.
> S를 알 때, 자연수 N의 최댓값은 얼마일까?접근
N개의 수를 다 더해서 S를 만들려고 할 때, 가장 많은 개수의 N개를 사용하려면 가장 작은 자연수 1부터 차례대로 모으고 모으면서 더해가면된다.
어디까지 더하는지는 더해서 나온 수가 S에서 뺐을 때, 남은수가 앞에서 이미 더한 수가 남게 되면 중복을 사용할 수 없기 때문에 해당 수가 남게되도록 더했던 수를 빼고, 남은 수를 통째로 더한(+1개)해주면 된다.
예를들어 20을 만든다고 하면 1,2,3...더해주며 20에서 뺴가며 확인한다. 1일떄, 20-1이 1보다 크므로 겹치지않아 가능해서 1사용하고, 남은 수는 19
2일 때, 19-2가 2보다 크므로 겹치지 않아 2사용하고 남은수는 17,
3일 때, 17-3이 3보다 크므로 겹치지 않아 3사용하고 남은수는 14,
4일 때, 14-4가 4보다 크므로 겹치지 않아 4사용하고 남은수는 10,
5일때, 10-5가 5가 되므로 이 경우 20을 만들기위해 1,2,3,4,5,5가 쓰여지게 되는것이다. 중복이 안되므로 5는 쓸 수 없어서 1,2,3,4까지 쓰고 남은 10을 사용해 총 5가지가 된다.
문제해결
> S의 범위가 INT형의 크기를 넘어가므로 Long형을 사용한다.
> 사용한 자연수의 개수를 누적할 cnt변수를 선언하고 앞서 유도한 로직을 구현한다.
> 자연수 1부터 시작해서 S-i가 i보다 커야 겁치지않아지므로 이를 확인하고 맞으면 개수누적, S갱신한다.
> S-i가 i와 같거나 작으면 해당 i는 사용하지 않고, 남갱신되어 남아있던 S를 사용한다.
> 이는 if문 밖의 cnt++인 개수를 한개 추가하고 끝낸다 를 의미한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//1789번 수들의 합
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long S = Long.parseLong(br.readLine());
int cnt = 0;
for(int i = 1; i <= S; i++) {
if(S - i > i) {
cnt++;
S -= i;
continue;
}
cnt++;
break;
}
System.out.print(cnt);
}
}
후기
개수를 많게 하려면 작은걸로 티끌모아서 만들어야 한다는건 알았지만 어떤식으로 중복없이 할까에서 고민을 좀 했다. boolean으로 방문처리할까 했지만 범위가 문제가 됐고 결국 S-i와 검증을 통해 이 i를 사용했을 때, 다음 i가 어때? 라는 미래시를 내다보는 검증식을 생각해냈다.
