[백준] 2851 슈퍼 마리오 - 누적합(Prefix Sum) JAVA

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

2851번: 슈퍼 마리오

 

코드설명

누적합 문제입니다.

 

1. 크기가 10인 배열 arr과 부분합을 저장할 배열 prefixSum을 초기화합니다.
2. 10번 반복하면서 각 배열의 값을 입력받고 부분합을 계산하여 prefixSum에 저장합니다.
3. 배열의 각 원소를 순회하면서 현재 위치까지의 부분합인 before와 다음 위치까지의 부분합인 after를 저장합니다.
4. 만약 after가 100 이상이면, 100에 가장 가까운 값을 찾습니다.
   • before와 after와 100과의 차이를 계산하여 어떤 값이 더 가까운지 비교합니다.
   • 가까운 값으로 answer를 업데이트하고 출력한 뒤 프로그램을 종료합니다.
5. 만약 모든 원소를 순회해도 100에 가까운 값이 나오지 않았다면, 마지막으로 계산된 answer를 출력합니다.

 

처음에 96프로에서 계속해서 통과를 못햇엇는데 이유는 answer의 갱신조건이 100보다 클 경우에만 작동했기때문입니다.

answer = after로 처리하여 무조건적으로 처리하도록 하여 100이 넘지않더라도 갱신되도록 했습니다.

출처 : https://www.acmicpc.net/board/view/100438

0
0
0
0
0
0
0
0
0
1

정답 : 1
내 오류 : 0



1
1
1
1
1
1
1
1
1
1

정답 : 10
내 오류 : 0

코드

위의 반례를 반영하여 마지막값까지 반영합니다. 처음부터 answer값에 after값을 삽입하여서 연산을 진행하고, 만약에 이후에 비교하여 before값이 after값보다 100보다 가까우면서 더 작은 조건을 만족한다면 변화시킵니다.

answer = after 연산을 통해 after는 항상 before보다 100에 가깝고, 만약 after >= 100 을 초과한다면 그때는 before와 비교연산하도록 처리합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int N, M, K, T;
	public static int answer = 0;
	public static int[] arr;
	public static int[][] map;
	public static int[] prefixSum;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	arr = new int[10];
    	prefixSum = new int[11];
    	for(int i=0;i<10;i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    		prefixSum[i+1] = prefixSum[i] + arr[i];  
		}
    	
    	int before = 0;
    	int after = 0;
    	for(int i=0;i<10;i++) {
    		before = prefixSum[i];
    		after = prefixSum[i+1];
    		answer = after;
    		if(after >= 100) { //만약 after가 100을 넘었다면 before값도 100과 가장 가까운값입니다.
				int diffBetweenBefore = Math.abs(100 - before);
				int diffBetweenAfter = Math.abs(100 - after);
				if(diffBetweenBefore < diffBetweenAfter) {
					answer = before;
				}else if(diffBetweenBefore >= diffBetweenAfter){
					answer = after;
				}
				System.out.println(answer);
    			return ;
    		}
		}
    	System.out.println(answer);
    	
    	
	}
}

 

 

처음에 마지막 값을 올바르게 갱신안한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int N, M, K, T;
	public static int answer = 0;
	public static int[] arr;
	public static int[][] map;
	public static int[] prefixSum;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	arr = new int[10];
    	prefixSum = new int[11];
    	for(int i=0;i<10;i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    		prefixSum[i+1] = prefixSum[i] + arr[i];  
		}
    	
    	int before = 0;
    	int after = 0;
    	for(int i=0;i<10;i++) {
    		before = prefixSum[i];
    		after = prefixSum[i+1];
    		if(after >= 100) { //만약 after가 100을 넘었다면 before값도 100과 가장 가까운값입니다.
				int diffBetweenBefore = Math.abs(100 - before);
				int diffBetweenAfter = Math.abs(100 - after);
				if(diffBetweenBefore < diffBetweenAfter) {
					answer = before;
				}else if(diffBetweenBefore >= diffBetweenAfter){
					answer = after;
				}
				System.out.println(answer);
    			return ;
    		}
		}
    	System.out.println(answer);
    	
    	
	}
}