[Java] 백준 11505번 구간 곱 구하기 문제 952hi의 접근방법

 

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

11505번: 구간 곱 구하기

---

 

1. 문제접근

 

구간 합이나 곱은 기존 for문 방식으로 더하거나 곱하면 만약 1~n까지의 합을 구해야 한다면 시간이 O(n) 소요된다. 하지만 이문제같은경우 100만개의 원소를 업데이트와 값갱신까지 계속 해서 한다면 더욱 많은 시간이 소요되기 때문에 세그먼트 트리 문제라고 확신을 가지고 문제를 풀게 되었습니다.

 

세그먼트 트리의 개념을 알고있다는 전제하에 작성한 풀이입니다.

 

이 문제를 풀려고 생각하면서 핵심 두 가지라고 생각했습니다.

1. 트리의 배열 크기를 얼마로 줄것인가?

2. 값업데이트를 어떤 방식으로 할것인가?

 

첫 번째 트리의 배열크기

트리의 배열 크기같은 경우 n개의 루트노트가 주어지기에 트리의 높이를 유추해 낼수있습니다.

n=5개라면 높이가 3보다 커야하고 5보다는 작은 상태입니다.

즉 2^4 -1  총 원소 수 15가 이므로 16을 배열의 크기로 주어야합니다 (루트 인덱스 1일 경우)

이 부분을 공식으로 바꾸면 (로그의 밑은 2 ) 

높이는 log 5   + 1 => log 5 는 2.xx 이므로 반올림

즉 높이는 3+1 => 4 

총원소의 개수는 2의 4승 -1 15가 나오게됩니다 

자바 코드로는 (int)Math.pow(2, (int)Math.ceil(Math.log(n)/Math.log(2))+1);

 

두 번째 값업데이틑 방식

더하기나 빼기 였다면 루트에서 리프노드까지 내려가면서 범위에 맞는 노드의 값을 업데이트 할 수있지만

곱하기의 경우 복잡해지고 제대로 되지않는 경우가 발생할 수가 있어서 리프에서 루트로 바텀업방식을 사용해야 겠다고 생각했습니다. 

2. 느낀점

세그먼트트리를 이해하고 있다면 실수는 크게 발생하지 않을 거라고 생각 했고 구간합문제는 몇개 풀어보면서 탑다운 방식 업데이트를 해서 문제를 풀었는데 이 문제를 풀면서 바텀업 방식 재귀함수를 통해 문제를 풀어서 좋았다.

3. 코드

import java.io.*;
public class boj11505 {
	static class Reader {
		int bfs = 1 << 16;
		byte[] buffer = new byte[bfs];
		int bufferPos = 0, bufferState = 0;
		DataInputStream dis = new DataInputStream(System.in);

		byte read() {
			if (bufferPos == bufferState) {
				try {
					bufferState = dis.read(buffer, bufferPos = 0, bfs);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (bufferState == -1)
					buffer[0] = -1;
			}
			return buffer[bufferPos++];
		}

		int nextInt() {
			int rtn = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				rtn = rtn * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -rtn;
			return rtn;
		}
	}
	static int n,MOD=1000000007,input[];
	static long tree[];
	public static void main(String[] args) throws IOException {
		StringBuilder sb =new StringBuilder();
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		Reader in = new Reader();
		n = in.nextInt();//리프노드의 개수
		int m = in.nextInt();
		int k = in.nextInt();
		int size = (int)Math.pow(2, (int)Math.ceil(Math.log(n)/Math.log(2))+1);// 리프노드의 개수 최소<n<최대 최대값찾기(트리높이)-> 높이를 알면 포화이진트리 개수를 알수 있다 
		input = new int[n+1]; // 1번 인덱스부터 한 이유는 자식이 2n , 2n+1 // 0이면 2n+1 , 2n+2
		tree = new long[size];
		
		for(int i=1;i<=n;i++) input[i] = in.nextInt();
		init(1,n,1); // 세그먼트 트리 생성
		
		int type,one,two;
		for(int i=0;i<m+k;i++) {// m와 k가 번갈아 나오기 때문에 총횟수만큼 반복하고 1,2냐에 따라 특정 함수 호출
			type = in.nextInt();
			one = in.nextInt();
			two = in.nextInt();
			if(type == 1) {
				input[one] = two;
				update(1,n,1,one,two);
			}else if(type==2) {
				sb.append(mul(1,n,1,one,two)).append("\n");
			}
		}
		sb.setLength(sb.length()-1);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
	// 구간값구하기
	private static long mul(int start, int end, int nodeidx, int minidx, int maxidx) {
		if(end<minidx || maxidx<start) return 1; // 구간벗어나면 계산에 합쳐지면 안되니 1리턴
		if(minidx<=start && end<=maxidx ) return tree[nodeidx]; // 범위안에 든다는 말은 그값을 그냥 바로 리턴해주면 된다는뜻
		int mid = (start+end)/2;
		return (mul(start,mid,nodeidx*2,minidx,maxidx)*mul(mid+1, end, nodeidx*2+1, minidx, maxidx))%MOD; 
	}
	// 값변경 리프노드에서 루트노드까지
	private static long update(int start, int end, int nodeidx, int idx, int val) {
		if(end<idx || idx<start) return tree[nodeidx];
		if(start==end) return tree[nodeidx]=val;  // 업데이트 하는 그놈이라면 
		int mid = (start+end)/2;
		return tree[nodeidx] = (update(start, mid, nodeidx*2, idx, val)*update(mid+1, end, nodeidx*2+1, idx, val))%MOD;
	}
	// 세그먼트 트리 초기화
	private static long init(int start, int end, int nodeidx) {
		if(start==end) return tree[nodeidx]=input[start]; // start end 같다라는 말은 1 1 즉 1번 값  ex 1 2 값 1~2곱값
		int mid = (start+end)/2;
		return tree[nodeidx] = (init(start, mid, nodeidx*2)*init(mid+1,end,nodeidx*2+1))%MOD;
	}
}

 

4. 시간 및 메모리

시간이랑 메모리 차이 많이내고 1등해서 기분이 좋았다.