728x90
문제
N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.
입력
첫째 줄에 2,000,000 이하의 자연수 N이 주어진다.
출력
첫 줄에 구하고자 하는 수를 출력한다.
첫번째 시도
1. 먼저 시간제한을 봤다.
2. while문으로 하나씩 증가시키면서 값을 찾는 무식한 방법이 가능할까?
3. 시간 제한상 불가능할 거라 생각했다.
두번째 시도
1. 규칙을 찾아보자
N = 1 -> x
N = 2 -> 3
N = 3 -> 4, 8
N = 4 -> 5, 10, 15
2. 나머지와 몫이 모두 같은 자연수의 갯수는 N-1개가 나온다.
3. 나머지와 몫이 모두 같은 자연수를 찾는다는 방법보다
나머지와 몫이 모두 같은 자연수를 만들어 가는 방법이 효율적이라고 생각했다.
즉
i <= N-1
(N * i(몫)) + i(나머지) = 나머지와 몫이 모두 같은 자연수로 등장한다.
반응형
'Basic > 코딩테스트' 카테고리의 다른 글
[실버 5, 1] 백준 16173, 16174번 자바(JAVA) - 점프왕 쩰리 (Small, Large) (0) | 2022.06.13 |
---|---|
[실버 4] 백준 5568번 자바(JAVA) - 카드 놓기 (0) | 2022.06.02 |
[브론즈 3] 백준 1547번 자바(JAVA) - 공 (0) | 2022.05.16 |
[브론즈 1] 백준 3054번 자바(JAVA) - 피터팬 프레임 (0) | 2022.05.15 |
[실버5] 백준 1094번 자바(JAVA) - 막대기 (0) | 2022.05.15 |