BOJ3078 좋은 친구(Java)

---

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

태그 : 누적 합

---

사고 과정

N이 30만 이내이고, 이름 길이가 최대 20인 조건을 보고,

바로 sum[300001][21] 테이블을 떠올렸다.

len[300001] 배열에 해당 인덱스의 이름의 길이를 저장해놓고,

sum[i + k][해당 길이] - sum[i][해당 길이] 로 모든 친구의 쌍을 구해줬다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
     
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
 
    static int N, K;
   
    static int [] len = new int [300001];
    static int [][] sum = new int [300001][21];
    static long ans;
     
    static void solve() throws IOException {
    	for(int i = 1; i <= N; ++i) {
    		String name = br.readLine().trim();
    		len[i] = name.length();
    		sum[i][len[i]]++;
    		for(int j = 2; j <= 20; ++j) {
        		sum[i][j] += sum[i - 1][j];	
    		}
    	}
    	
    	for(int i = 1; i < N; ++i) {
    		int next = Math.min(N, i + K);
        	ans += (sum[next][len[i]] - sum[i][len[i]]);
    	}
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        
    	st = new StringTokenizer(br.readLine().trim());
    	N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        solve();
        
        System.out.println(ans);
    }
}

---

후기

G4 치고 매우 쉬운 난이도였던 것 같다.