백준 5676 (음주 코딩)

문제

---

오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다.

상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다.

먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X1, X2, ... XN을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다.

• 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다.
• 곱셈: 선영이는 상근이에게 i와 j를 말한다. 상근이는 Xi × Xi+1 × ... × Xj-1 × Xj 의 값이 양수인지, 음수인지, 0인지를 대답한다.

곱셈 명령에서 상근이가 대답을 잘못했을 때의 벌칙은 소주 한 잔이다. 상근이는 갑자기 대회가 걱정되기 시작했다. 또, 상근이는 발머의 피크 이론을 증명하고 싶지 않다.

다행히 선영이는 상근이에게 노트북 사용을 허락했다. 상근이는 자신의 수학 실력보다 코딩 실력을 더 믿는다.

상근이를 돕는 프로그램을 작성하시오.

 

 

 

 

풀이

---

Segment Tree 의 구간곱을 사용하면 쉽게 풀수 있다.

하지만 이문제의 핵심은 음수, 양수, 0 만 판단해 주면 된다.

 

따라서 저장을 -1, 1, 0 으로 하여 곱을 했을 때 부호를 구했다.

 

트리를 저장하는 코드를 보면

public static int init(int start, int end, int node) {
    	
   	if(start == end) {
   		if(list[start] > 0 ) {
   	   		return tree[node] = 1;
  		}
   		else if(list[start] == 0) {
   	   		return tree[node] = 0;
   		}
   		else {
  	   		return tree[node] = -1;   			
   		}

   	}
   	
   	int mid = (start + end) / 2;
   	    	
   	return tree[node] = init(start, mid, 2* node) * init(mid + 1, end, 2 * node + 1);
}

 

이와 같이 tree[node] 에 저장할 때 list[] 의 값이 음수, 양수, 0 이냐에 따라 값을 -1, 1, 0 으로 넣어주면 값이 overflow 가 발생하는 오류를 줄일 수 있다.

 

나머지 부분은 부분합, 부분곱 문제와 동일 하기에 따로 설명하지 않겠다.

 

conpulake.tistory.com/53

백준 11505 ( 구간 곱 구하기 )

conpulake.tistory.com/50

백준 1275 ( 커피숍 2)

위의 문제들을 통해 Segment Tree 를 보면 더 좋을 것 같다.

 

이문제에서는 종료 조건이 EOF(End Of File) 이므로 이점을 유의해야한다.

<전체코드>

import java.io.*;
import java.util.*;


public class Main {
	
	static StringBuilder sb = new StringBuilder();
	static int[] tree;
	static int[] list;
	
    public static void main(String[] args) throws IOException {
       BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
       String input;
       while( (input = bufferedReader.readLine()) != null) {
        	StringTokenizer st = new StringTokenizer(input);
        	
        	int n = Integer.parseInt(st.nextToken());
        	int k = Integer.parseInt(st.nextToken());
        	
        	tree = new int[4 * (n + 1)];
        	list = new int[n +1];
        	
        	
        	st = new StringTokenizer(bufferedReader.readLine());
        	
        	for(int j = 1 ; j <= n ; j++) {
        		list[j] = Integer.parseInt(st.nextToken()); 
        	}
        	
        	init(1, n, 1);
        	
        	for(int j = 0 ; j < k ; j++) {
        		st = new StringTokenizer(bufferedReader.readLine());
        		
        		String doing = st.nextToken();
        		int a = Integer.parseInt(st.nextToken());
        		int b = Integer.parseInt(st.nextToken());
        		
        		if(doing.equals("C")) {
        			update(1, n, 1, a, b);
        		}
        		else if(doing.equals("P")) {
        			int result = query(1, n, 1, a, b);
        			if(result > 0) {
        				sb.append("+");
        			}
        			else if(result == 0) {
        				sb.append("0");
        			}
        			else {
        				sb.append("-");
        			}
        		}
        	}
        	sb.append("\n");
        }
        
        System.out.println(sb);
    }
    
    public static int init(int start, int end, int node) {
    	
    	if(start == end) {
    		if(list[start] > 0 ) {
    	   		return tree[node] = 1;
    		}
    		else if(list[start] == 0) {
    	   		return tree[node] = 0;
    		}
    		else {
    	   		return tree[node] = -1;   			
    		}
 
    	}
    	
    	int mid = (start + end) / 2;
    	    	
    	return tree[node] = init(start, mid, 2* node) * init(mid + 1, end, 2 * node + 1);
    }
    
    
    public static int update(int start, int end, int node, int n, int num) {
    	
    	if(start == end) {
    		if(num > 0) {
    			return tree[node] = 1;
    		}
    		else if(num == 0) {
    			return tree[node] = 0;
    		}
    		else {
    			return tree[node] = -1;
    		}
    	}
    	
    	int mid = (start + end) / 2;
    	
    	if(mid >= n) {
    		return tree[node] =  tree[2 * node + 1] * update(start, mid, 2*node, n, num);
    	}
    	else {
    		return tree[node] = tree[2 * node] * update(mid + 1, end, 2 * node + 1, n, num);
    	}
    }
    
    public static int query(int start, int end, int node, int a, int b) {
    	
    	if(start > b || end < a) {
    		return 1;
    	}
    	else if(start >= a && end <= b){
    		return tree[node];
    	}
    	else {
    		int mid = (start + end) / 2;
    		
    		return query(start, mid, 2 * node, a, b) * query(mid + 1, end, 2 * node + 1, a, b);
    	}
    }
}