[코드트리/NOVICE MID] 바구니 안의 사탕 2 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        int N = Integer.parseInt(st.nextToken());   // 바구니 수
        int K = Integer.parseInt(st.nextToken());   // +- K
 
        int[] arr = new int[301];
 
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int candy = Integer.parseInt(st.nextToken());   // 사탕 개수
            int basket = Integer.parseInt(st.nextToken());  // 바구니 좌표
 
            arr[basket] += candy; // 여러 바구니가 놓여있을 수 있으므로 누적
        }
 
        int max = 0;
        for(int i = K ; i < arr.length ; i++) { // 중간점
            int tmp = 0;
            for(int j = i - K ; j <= i + K && j <= 300 ; j++) { // 끝점
                tmp += arr[j];
            }
            max = Math.max(max, tmp);
        }
 
        System.out.println(max);
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색

- 중간 지점 i : K부터 배열의 최대 길이까지

- 끝점 : (i - K)부터 (i + K)까지. 그런데 이 값이 범위를 벗어나면 안 됨. (그래서 j <= 300했음)

 

중간 지점을 정하고, (중간 지점 - K, 중간 지점 + K)까지의 원소의 합을 구한다.

최댓값과 비교해 갱신한다.

 

 

 

 

---

🔺 다른 풀이들

import java.util.Scanner;
 
public class Main {
    public static final int MAX_NUM = 100;
    
    public static int n, k;
    public static int[] arr = new int[MAX_NUM + 1];
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt();
        k = sc.nextInt();
 
        for(int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int x = sc.nextInt();
            
            arr[x] += a;
        }
        
 
        int maxSum = 0;
        for(int i = 0; i <= MAX_NUM; i++) {    // 시작점
 
            int sum = 0;    // 해당 구간 내 원소의 합
 
            for(int j = i - k; j <= i + k; j++)    // 구간 : [i-K, i+K]
                if(j >= 0 && j <= MAX_NUM)    // 범위 내에 이ㅆ도록
                    sum += arr[j];
 
            maxSum = Math.max(maxSum, sum);    // 최댓값 갱신
        }
                            
        System.out.print(maxSum);
    }
}

 

 

---

💬 느낀 점

범위만 잘 잡으면 빨리 풀 수 있는데...

엄한데서 시간 잡아먹음.....

테스트케이스를 만들어 풀어보자....ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V