3개의 풀이가 나왔다.

1. 시간초과

하나씩 다 더해줌

2. 런타임

2차원 배열을 만들어서 무게별로 나누고 또 거기에서 컬러별로 나눴음

2000 * 2e5 * 4 = 1G가 넘어가서 런타임 에러

3. 정답

블로그를 조금 참고했지만, 짜고나니 거의 똑같게 나옴...

total 스코어 idea를 참고함.

import java.util.*;
import java.io.*;
/**
* BOJ 10800 컬러볼 풀이
* https://gist.github.com/KSH-code/e705293348cbd1aea4567002e516a388
*/
class Ball implements Comparable<Ball>{
public int color, weight, idx;
public Ball(int color, int weight, int idx){
this.color = color;
this.weight = weight;
this.idx = idx;
}
@Override
public int compareTo(Ball arg){
return this.weight - arg.weight;
}
}
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));
int N = Integer.parseInt(br.readLine());
int score[] = new int[N];
int color[] = new int[N+1];
int total = 0;
Ball temp[] = new Ball[N];
for(int i = 0; i<N; i++){
String str1[] = br.readLine().split(" ");
int c = Integer.parseInt(str1[0]);
int w = Integer.parseInt(str1[1]);
temp[i] = new Ball(c, w, i);
}
Arrays.sort(temp);
for(int i = 0, j = 0; i<N; i++){
for(; temp[j].weight<temp[i].weight; j++){
total += temp[j].weight;
color[temp[j].color] += temp[j].weight;
}
score[temp[i].idx] += total - color[temp[i].color];
}
for(int i = 0; i<N; i++){
bw.write(score[i] + "\n");
}
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 2188 풀이 (이분매칭)  (0) 2017.11.08
BOJ 10803 풀이  (1) 2017.11.06
BOJ 10797 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 초등부 1번)  (0) 2017.10.27
BOJ 3653 영화 수집 풀이 Fenwick Tree(Binary Indexed Tree)  (0) 2017.10.27
BOJ 1907 풀이 (Olympiad > Croatian Highschool Competitions in Informatics > 2005 > Regional Competition - Juniors 3번)  (0) 2017.10.26

Segment Tree

BOJ에 있는 블로그를 보고 공부했다.

일단 노트에 트리를 그리면서 어떤식으로 작동하는지 알게됐고, 아직 익숙하지 않다.


재귀함수 덩어리.

import java.util.*;
import java.io.*;
/**
* BOJ https://www.acmicpc.net/problem/2042 구간 합 구하기
* https://gist.github.com/KSH-code/ca97b2ae1995e8746090b0817989d3c3
*/
class Main{
private static int value[];
private static long node[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str1[] = br.readLine().split(" ");
int N = Integer.parseInt(str1[0]); // 총 갯수
int M = 0; // 연산할 갯수
M += Integer.parseInt(str1[1]) + Integer.parseInt(str1[2]);
int H = (int) Math.pow(2.0, Math.floor((Math.log(N) / Math.log(2.0)) + 1));
value = new int[N];
node = new long[2 * H];
for(int i = 0; i<N; i++){
value[i] = Integer.parseInt(br.readLine());
}
init(1, 0, N-1);
for(int i = 0; i<M; i++){
String str2[] = br.readLine().split(" ");
int a = Integer.parseInt(str2[0]);
int b = Integer.parseInt(str2[1]);
int c = Integer.parseInt(str2[2]);
if(a == 1){
long diff = c-value[--b];
value[b] = c;
update(1, 0, N-1, b, diff);
}else{
bw.write(sum(1, 0, N-1, b-1, c-1)+"\n");
}
}
bw.flush();
}
private static long init(int idx, int start, int end){
if (start == end) {
return node[idx] = value[start];
} else {
return node[idx] = init(idx*2, start, (start+end)/2) + init(idx*2+1, (start+end)/2+1, end);
}
}
private static long sum(int idx, int start, int end, int left, int right){
if (left > end || right < start) {
return 0;
}
if(left <= start && right >= end){
return node[idx];
}
return sum(idx*2, start, (start+end)/2, left, right) + sum(idx*2+1, (start+end)/2+1, end, left, right);
}
private static void update(int idx, int start, int end, int change, long diff){
if (change < start || change > end) return;
node[idx] = node[idx] + diff;
if (start != end) {
update(idx*2, start, (start+end)/2, change, diff);
update(idx*2+1, (start+end)/2+1, end, change, diff);
}
}
}
view raw Main.java hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 2951 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 5번 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 중등부 3번)  (0) 2017.10.25
BOJ 2590 색종이 풀이(Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 4번 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 중등부 2번)  (0) 2017.10.25
BOJ 2589 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 3번)  (0) 2017.10.23
BOJ 12852 1로 만들기 2 풀이  (0) 2017.10.20
2611 자동차경주 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 5번)  (0) 2017.10.20

음 보물찾기 문제.. BFS


BFS를 사용하며 visited를 잘못써서 시간초과가 났었고, for문을 break하는걸 넣어놓고 안빼서 계속 틀렸었다.

2005년도 초등생은 BFS를 할줄 안다니.. 대단하네


import java.io.*;
import java.util.*;
/**
* BOJ 2589 보물섬
* https://gist.github.com/KSH-code/ceff9760ed82ffd647570dae9349a4da
*/
public class Main{
private static int N,M;
private static int result = 0;
private static int go[] = {-1, -1, 1, 1};
private static boolean map[][];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1[] = br.readLine().split(" ");
N = Integer.parseInt(str1[0]);
M = Integer.parseInt(str1[1]);
map = new boolean[N][M];
for(int i = 0; i<N; i++){
String str2[] = br.readLine().split("");
for(int j = 0; j<M; j++){
map[i][j] = str2[j].equals("L");
}
}
for(int i = 0; i<N; i++){
for(int j = 0; j<M; j++){
if(map[i][j]){
BFS(i, j);
}
}
}
System.out.println(result);
}
private static void BFS(int x, int y){
boolean visited[][] = new boolean[N][M];
int time[][] = new int[N][M];
Queue<Integer> queue = new LinkedList<>();
queue.offer(x*100+y);
visited[x][y] = true;
while(!queue.isEmpty()){
int poll = queue.poll();
int tempX = poll / 100;
int tempY = poll % 100;
for(int i = 0; i<4; i++){
int s = tempX;
int e = tempY;
if(i % 2 == 0){
s += go[i];
}else{
e += go[i];
}
if(s < 0 || s >= N || e < 0 || e >= M || visited[s][e] || !map[s][e]) continue;
visited[s][e] = true;
time[s][e] = time[tempX][tempY] + 1;
queue.offer(s * 100 + e);
result = Math.max(result, time[s][e]);
}
}
}
}
view raw Main.java hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 2590 색종이 풀이(Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 4번 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 중등부 2번)  (0) 2017.10.25
BOJ 2042 구간 합 구하기 풀이  (0) 2017.10.24
BOJ 12852 1로 만들기 2 풀이  (0) 2017.10.20
2611 자동차경주 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 5번)  (0) 2017.10.20
BOJ 2016 풀이 2004 (한국정보올림피아드시․도지역본선)  (0) 2017.10.19

+ Recent posts

티스토리툴바