글 읽기 - 1517번 총 횟수 구할 때 질문드립니다.

julie0964 2년 전 0

총횟수를 구할 때 cnt+=j-i라고 써줬는데 다른 분들 성공시킨 코드를 보니까 cnt+=mid-i+1 이라고 쓰신 것을 봤습니다.

j-i를 더했을 때와 mid=i-1를 더했을 때의 차이점이 어디서 생기는지 궁금합니다.

감사합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int n;
	public static long[] arr;
	public static long[] sorted;

	public static long cnt;

	// 분할

	public static void mergeSort(long arr[], int start, int end) {
		if (start < end) {
			int middle = (start + end) / 2;
			mergeSort(arr, start, middle);
			mergeSort(arr, middle + 1, end);
			merge(arr, start, middle, end);
		}
	}

	public static void merge(long[] arr, int start, int middle, int end) {
		int i = start;
		int j = middle + 1;
		int k = start;

		while (i <= middle && j <= end) {
			if (arr[i] <= arr[j]) {
				sorted[k] = arr[i];
				i++;

			} else {
				cnt += j - i;  
				sorted[k] = arr[j];
				j++;

			}
			k++;
		}

		if (i > middle) {
			
			for (int t = j; t <= end; t++) {
				sorted[k] = arr[t];
				k++;
			}
		} else {
			
			for (int t = i; t <= middle; t++) {
				sorted[k] = arr[t];
				k++;
			}
		}

		for (int t = start; t <= end; t++) {
			arr[t] = sorted[t];

		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		cnt = 0;
		arr = new long[n];
		sorted = new long[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}

		mergeSort(arr, 0, n - 1);

		System.out.println(cnt);

	}

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1517번 총 횟수 구할 때 질문드립니다.

julie0964 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말