[SCPC - 2019년 1차 예선] 오르락 내리락 (JAVA)

풀이

1 이상의 정수를 받아서 다음의 규칙에 따른 “작업”을 반복하여 결국 1 을 만드는 게임을 하려고 한다. 아래 규칙은 한번의 작업에 대한 것이고, 작업의 결과로 만들어지는 수에 작업을 수행하는 것을 반복한다.

 

규칙에도 나와 있듯이 현재 수가 1 인 경우는 작업을 하지 않고 멈춘다. 1. 만약 수가 1 이면 작업을 하지 않고 멈춘다. 2. 만약 수가 1 이 아닌 홀수이면 1 을 더한다. 3. 만약 수가 짝수이면 2 로 나눈다.

 

예를 들어, 받은 수가 2 인 경우는 2→1 로 1 회의 작업 후에 멈춘다. 받은 수가 4 인 경우는 4→2→1 로 2 회의 작업 후에 멈춘다. 받은 수가 3 인 경우는 3→4→2→1 로 3 회의 작업 후에 멈춘다. 받은 수가 6 인 경우는 6→3→4→2→1 로 4 회의 작업 후에 멈춘다.

 

앞의 예 들에서 볼 수 있듯이, 받은 수가 3 인 경우의 작업 횟수를 알면 받은 수가 6인 경우의 작업 횟수를 바로 계산할 수 있다는 것을 알 수 있다. 두 정수 N1과 N2를 입력으로 받아서 (1≤N1≤N2≤106), N1,N1+1,N1+2,…,N2의 작업 회수를 모두 더한 값을 계산하는 프로그램을 작성하라.

 

 

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고, 이후 차례로 T 개의 테스트 케이스가 주어진다. (1≤T≤10,000)

 

각 테스트 케이스의 첫 줄에는 정수 N1과 N2가 주어진다. (1≤N1≤N2≤10^6)

- 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 100점) 주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며, 각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.

 

ㆍ 그룹 1 (34점) : 이 그룹의 테스트 케이스에서는 1≤N1≤N2≤10^3.

ㆍ 그룹 2 (66점) : 이 그룹의 테스트 케이스에서는 원래의 조건 외에는 다른 제약조건이 없다.

 

 

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다. 그 다음 줄에, N1,N1+1,N1+2,…,N2의 작업 회수를 모두 더한 값을 출력한다.

 

 

풀이

다이나믹 프로그래밍과 세그먼트 트리(혹은 부분 합 알고리즘)를 이용하여 풀 수 있는 문제였습니다.

 

세그먼트 트리가 처음이신 분은 아래 포스팅을 정독하시길 바랍니다.

 

 

[BOJ] 백준 2042번 : 구간 합 구하기 (JAVA)

 

 

문제에서는 특정 수에 대하여 1로 만드는 데 몇 회의 작업해야하는지 구하는 것을 요구하였습니다.

먼저, 1부터 6까지 어떤 식으로 규칙이 있는지 살펴봅시다.

 

1은 바로 일을 하지 않고 종료하므로 dp[1] = 0이 됩니다.

2는 짝수이므로 2 -> 1 로 바꾸는 데 총 1회의 작업이 필요하므로 dp[2] = 1이 됩니다.

 

3은 홀수이므로 3 -> 4 -> 2 -> 1로 바꾸는 데 총 4회의 작업이 필요하나, dp[4]에 대한 정보가 없어서 dp[3]을 구할 수는 없습니다.

4는 짝수이므로 4 -> 2 -> 1로 바꾸는데 총 2회의 작업이 필요합니다. 이 때, 2 -> 1로 바꾸는 작업이 dp[2]로 이미 저장되어있기때문에 dp[4] = dp[2] + 1이라 할 수 있습니다.

 

여기서 알 수 있는 사실이 특정 짝수에 대한 작업을 알기 위해서 (짝수 - 1)에 대한 작업을 알 필요는 없다는 것입니다.

따라서 dp[1] = 0, dp[2] = 1로 설정한 뒤, dp[4] = dp[2] + 1, dp[3] = dp[4] + 1 순서로 bottom-up 방식으로 dp 배열을 채워나가시면 됩니다.

 

dp 배열의 사이즈를 10^6까지 지정하여 위의 과정을 취한뒤, 최대 10^4개의 테스트 케이스를 수행하게 됩니다.

저는 단순히 dp[n1] ~ dp[n2]까지 반복문을 통하여 값을 모두 더했지만, 시간 초과가 발생하였습니다.

 

따라서 dp의 구간 합을 저장하는 세그먼트 트리를 정의하기로 결정하였습니다.

(아래 풀이2에서는 부분 합 알고리즘으로 설명할 예정입니다.)

 

방식은 전형적인 세그먼트 트리인 init과 sum을 이용합니다.

 

테스트 케이스를 수행하기 전에 init 과정을 취하고, 테스트 케이스 안에서 sum 과정을 순차적으로 수행하시면 됩니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

 

풀이2 - 추가

위에서는 세그먼트 트리로 풀었지만, 사실 세그먼트 트리 필요 없이 부분 합 알고리즘만 이용하여 풀 수 있습니다.

결국, 우리가 필요한건 특정 구간의 합이기때문에 psum[1] = dp[1]로 설정한 뒤, psum[i] = psum[i - 1] + dp[i] 라는 식을 통해, psum[i] : dp[1] + ... + dp[i] 까지의 합을 정의하면 됩니다.

 

이후, psum[n2] - psum[n1 - 1]을 통해 원하는 합을 구할 수 있습니다.

이 부분에 대한 소스코드를 아래 올려두었습니다.

 

 

소스코드

 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.