최솟값과 최댓값
그냥 세그먼트 트리로 최소트리, 최대트리 구현하면 끝나는 문제이다.#include#includeusing namespace std;long long arr[100004];long long max_seg[300004],min_seg[300004];int N,M;void max_init(int n, int s, int e){ if(s==e) { max_seg[n] = arr[s]; return; } int m = (s+e)/2; max_init(n*2,s,m); max_init(n*2+1,m+1,e); max_seg[n] = max(max_seg[n*2],max_seg[n*2+1]); return;}long long min_init(int ..
구슬 탈출 2
그냥 간단한 dfs/bfs 문제이다. dfs로 풀어도 되겠지만 10번 이하로 구슬을 빼내야 하는 조건이 있길래 bfs로 풀어봤다.#include#includeusing namespace std;int board[100][100]; //.은 0, #는 1, O는2int N,M;int ans = 0;struct state{ int rx,ry,bx,by,num;};int wx[4]={0,0,1,-1};int wy[4]={1,-1,0,0};queueescape;state mov(int i, state curr){ int bc=0,rc=0; while(board[curr.bx][curr.by]==0) { curr.bx+=wx[i]; curr.by+=wy[i]; ..
구간 합 구하기
중간에 수를 바꾸고 구간 합을 구하는 문제이다.그냥 세그먼트 트리를 쓰면 바로 풀린다.#includeint N, M, K;long long arr[1000004];long long sum[3000004];long long init(int n, int s, int e){ if(s==e) return sum[n] = arr[s]; int m = (s+e)/2; return sum[n] = init(n*2, s, m) + init(n*2+1, m+1, e);}long long fin(int n, int s, int e, int fs, int fe){ if(efe) return 0; if(fse) return; sum[n] += diff; if(s!=e) { ..
빵집
dfs와 그리디 알고리즘이 합쳐진 문제이다.왼쪽에서 오른쪽으로 이동을 하는데 왼쪽의 R개의 점에 대해서 다 탐색을 해봐야 한다.여기서 그리디를 적용해야 하는데 길이 겹치면 안되기 때문에 길 하나를 찾아도 최대한 나머지 길들에 영향을 주지 않아야 한다.즉, 위에서부터 (1,1)부터 (R,1)까지 R번의 dfs를 도는데 최대한 위로 가야 아래쪽에서 영향을 안 받는다.오른쪽 위, 오른쪽, 오른쪽 아래 순으로 탐색을 해 나가면 된다.int main(){ scanf("%d %d",&R,&C); for(int i=1;iarr 배열 안에 건물의 상태를 담고, dfs를 왼쪽 시작점들에 대해서 탐색한다.int path[504];int wx[3]={-1,0,1},wy[3]={1,1,1};bool dfs(int ..
저울
저울들을 합쳐서 만들 수 없는 무게를 구하면 된다.간단하게 풀 수 있는데 그냥 무게들을 정렬해 놓고 작은 것부터 더해 나가다가 다음 무게가 이전까지의 모든 무게의 합보다 커버리면 무게의 합+1부터는 만들 수 없다고 판단하면 된다.좀 더 자세히 설명해보자면, 작은것부터 큰것까지 무게들을 정렬했을 때 1번째부터 n번째 무게까지의 합을 sum_n이라고 하자.그리고 1,2,3,...., sum_n은 전부 다 만들 수 있다고 가정하자.이 때 sum_n보다 n+1번째 무게가 작다면, sum_n과 n+1번째 무게의 합 즉, 1부터 sum_(n+1) 까지도 전부 다 만들 수 있다.(1,2,3,..., sum_n을 만들 수 있다고 가정했기 때문에 n+1번째 무게에 1,2,..., sum_n을 더하면 되기 때문)만약 su..
