[백준 24267/Java] 알고리즘 수업 - 알고리즘 수행 시간 6

문제

---

24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6

 

풀이 과정

---

 

n값이 7인 경우를 생각해 보겠습니다. 이 경우, i값은 1 ~ 5까지 될 수가 있습니다.

i = 1이면, j의 값은 2 ~ 6가 될 수 있고, j값이 2이면, k의 값은 3 ~ 7이 될 수 있으므로 코드 1의 수행 횟수는 5회가 됩니다.

j	k의 범위	수행 횟수
2	3 ~ 7	5
3	4 ~ 7	4
4	5 ~ 7	3
5	6 ~ 7	2
6	7 ~ 7	1

이를 종합하면 i = 1인경우, 코드 1의 수행횟수는 (5+4+3+2+1)이 됩니다.

마찬가지로 i = 2이면, 코드 1의 수행횟수는 (4+3+2+1)이 됩니다.

결국 n의 값이 7이면, 코드 1의 수행횟수는 (5+4+3+2+1) + (4+3+2+1) + (3+2+1) + (2+1) + (1) = 35회가 됩니다.

n의 값이 6이라면, 수행횟수는 (4+3+2+1) + (3+2+1) + (2+1) + (1)이 될 것입니다.

이를 코드로 나타내면 아래와 같습니다.

public class 알고리즘의_수행_시간6 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		long sum = 0;   //총 수행 횟수
		long preSum = 0;
		for(int i = 1; i <= n-2; i++) {
			sum += (preSum + i);
			preSum += i;
		}
        
		bw.write(String.valueOf(sum) + "\n");
		bw.write("3");
		bw.flush();
		bw.close();
		br.close();
	}
}

여기서 preSum은 현재 i값을 제외한 이전 i값들의 합을 의미합니다.

i = 5인 경우, preSum값은 (4+3+2+1)을 의미하고 (preSum + i) 값은 (10 + 5)를 의미합니다.

 

다른 분들의 풀이

---

저는 위와 같은 방법으로 풀었지만, 다른 분들의 풀이를 보면 아래와 같은 식을 사용하는 것을 알 수 있었습니다.

총 수행 횟수 = (N*(N-1)*(N-2)/6)

N값에 7을 넣으면 35가 되는 것을 확인할 수 있습니다.

 

N = 6인 경우를 예시로 들어보겠습니다.

i값은 1,2,3,4가 될 수 있습니다.

i값이 1이면, j값은 2,3,4,5가 될 것입니다.

j값이 2이면, k값은 3,4,5,6이 될 것입니다.

즉, 1 부터 6까지의 숫자 중 3가지를 중복 없이, 크기 순으로 작성하는 경우의 수가 수행 횟수가 됩니다.

123, 124, 125, 126, 134, 135, 136, ... 345, 356, 456

이를 식으로 나타내면 아래와 같습니다.

 

참고자료

---

[BOJ] 백준 24267 알고리즘 수업 - 알고리즘의 수행 시간 6 (Swift)