백준 1834번 나머지와 몫이 같은 수 :: 마이구미

이번 글은 백준 알고리즘 1834번 문제를 다뤄보겠다.

문제의 제목은 "나머지와 몫이 같은 수" ..

흠 뭔가 쉬워보인다.

하지만 정답률은 34% 낮은 편이다.

난 수학을 좋아했지만 못한다....

난 그냥 노가다다.. 걍 노가다 하다보면 규칙이 나올 때가 있지 않느냐?

이 문제도 그렇다. 

일단 문제를 보자.

N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.

문제는 쉽게 이해할 수 있을 것이다.

이런 문제 나오면 난 그냥 규칙부터 찾아본다.

일단 나머지는 나누는 수보다 클 수 없을테고...

뭐 이런 것들 생각해볼 수도 있지만 일단 걍 해보자.

N = 1일때는 없군,

N = 2일때는 3

N = 3일때는 4, 8

N = 4일때는 5, 10, 15

규칙이 보이는가?

눈치 채라!

1. N-1 은 나머지와 몫이 같은 자연수 갯수.

2. 나머지와 몫이 같은 자연수는 배수관계. (4, 8), (5, 10, 15)...

이 규칙 가지고만 해도 충분하다.

for문 한번 돌리면 끝이다.

그리고 조건이 2000000 이하의 자연수이다.

N이 2000000으로 주어졌을 때 나머지와 몫이 같은 자연수 갯수는 1999999개가 된다.

그렇다면 최대 숫자는 2000000 * 1999999 = 3.999998e+12

int을 넘어버리기 때문에 long을 사용하였다.

알고나면 굉장히 쉬운 문제이다.

import java.util.Scanner;
 
public class Main {
     
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
         
        long num = sc.nextLong();
        long sum  = 0;
        for(long i=1;i<num;i++)
        {
            sum += (num+1)*i;
        }
 
        System.out.println(sum);
 
    }
}

백준 1834번 문제 - 나머지와 몫이 같은 수

https://www.acmicpc.net/problem/1834