BAEKJOON / 백준 - JAVA 31882번 근수

2024.06.10기준 - 실버4

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 근수 점수를 계산해서 총 합을 출력하는 문제입니다.

이 문제의 조건은

1. 부분 문자열 2는 '근수'로 간주하여 등장할 때마다 1점을 더합니다.
2. 부분 문자열 22는 '근근수'로 간주하여 등장할 때마다 2점을 더합니다.
3. 연속된 k개의 2로 이루어진 부분 문자열 22...2는 '근근...근수'로 간주하여 등장할 때마다 k점을 더합니다.
4. 그 외 부분 문자열은 0점을 더합니다.

저의 접근은 전체 길이에 따른 점수를 다 구한 뒤 길이에 맞춰 총 점을 더하는 방식을 선택했습니다.

StringTokenizer st = new StringTokenizer(br.readLine(), "134567890");

StringTokenizer을 통해 2를 제외한 모든 숫자는 0점이기 때문에 제외해줬습니다.

 

그런 뒤

BigInteger[] score = new BigInteger[1000001]; // 전체 스코어를 저장한다.
score[1] = BigInteger.valueOf(1);
score[2] = BigInteger.valueOf(4);
		
for (int i = 3; i < 1000001; i++) {
	// 뒤에 2번째에 있는것 보다 i * i 를 더하면 그 길이에 맞는 총 점수가 나온다.
	score[i] = new BigInteger(String.valueOf(score[i - 2].add(BigInteger.valueOf(i).multiply(BigInteger.valueOf(i)))));
}

점수를 계산을 해주었는데

여기서 문제점은 점수가 점점 너무 커져버려 int, long으로는 점수를 저장할 수 없게 되었습니다.

그래서 선택한 방법은 BigInteger을 사용하여 점수를 저장했습니다.

 

뒤에 2번째에 있는 것 보다 i * i 를 더하면 그 길이에 맞는 총 점수가 나온다는걸 알아 냈습니다.

그런 다음 2로만 나누어진 부분 문자열의 길이를 통해 전체 스코어인 count 변수에 더해 저장했습니다.

 

아직 부족한 점이 많아 빠르게 해결하지는 못하고, 실행 시간을 생각보다 많이 잡아먹은 코드였던거 같습니다..!

 

 

코드

package Main;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		br.readLine(); // 문자열의 길이
		StringTokenizer st = new StringTokenizer(br.readLine(), "134567890"); // 문자열을 2를 제외하고 없애준다.
		
		BigInteger[] score = new BigInteger[1000001]; // 전체 스코어를 저장한다.
		score[1] = BigInteger.valueOf(1);
		score[2] = BigInteger.valueOf(4);
		
		for (int i = 3; i < 1000001; i++) {
			// 뒤에 2번째에 있는것 보다 i * i 를 더하면 그 길이에 맞는 총 점수가 나온다.
			score[i] = new BigInteger(String.valueOf(score[i - 2].add(BigInteger.valueOf(i).multiply(BigInteger.valueOf(i)))));
		}
		
		BigInteger count = BigInteger.valueOf(0); // 총 근수
		while (st.hasMoreElements()) {
			count = count.add(score[st.nextToken().length()]); // 문자열 길이로 총 근수 합을 구한다.
		}
		
		bw.write(count.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}