k-1층의 1~b호 까지의 사람들이 k층 b호에 살아야 된다.

0층 i호에는 i명이 산다.


배열이

1 2 3 4 5

1 3 6 10 15

이런식으로 만들어진다.

위에서 부터 0층 1층 으로 계산했을때

d[i][j] = d[i-1][j] + d[i][j-1] 이다.


그래서 처음 입력받기 전에 초기화해주고 

입력받는 값으로 배열에 대입해서 출력하면 된다.

#include <cstdio>
/**
* https://www.acmicpc.net/problem/2775
* BOJ 백준온라인져지 2775 부녀회장이 될테야 풀이
*/
#define MAX 15
int main(){
int T,k,n;
scanf("%d", &T);
int d[MAX][MAX] = {};
for(int i = 1; i<MAX; i++){
d[0][i] = i;
d[i][1] = 1;
}
for(int i = 1; i<MAX; i++){
for(int j = 2; j<MAX; j++){
d[i][j] = d[i][j-1] + d[i-1][j];
}
}
while(T--){
scanf("%d%d",&k,&n);
printf("%d\n",d[k][n]);
}
return 0;
}
view raw BOJ_2775.cpp hosted with ❤ by GitHub


저작자표시

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

BOJ 백준온라인져지 6064 카잉 달력 풀이  (0) 2017.11.14
BOJ 백준온라인져지 1475 방 번호 풀이  (0) 2017.11.13
BOJ 백준온라인져지 10250 ACM 호텔 풀이  (0) 2017.11.12
BOJ 백준 1011 Fly me to the Alpha Centauri 풀이 Raw  (0) 2017.11.12
BOJ 2188 풀이 (이분매칭)  (0) 2017.11.08

H * W 호텔에서 N번째 사람이  어디에 들어가는지 구하는 문제.

첫 번째 문제를 푼 아이디어는

(N/H+1)*100+N/H+1

이였다. 

일단 내가 W에 대해 아무것도 작성하지 않은 이유는 굳이 W까지 해서 계산할 필요 없이 나눈값 + 1이 들어가기 때문이다.

근데 이 풀이는 N과 H가 같으면 출력이 잘못된다.


그래서 반복문으로 N에 H를 빼면서 W를 1씩 더해주면서 호수를 구해줬다.


코드를 보는게 이해가 더 쉽게 될 것이다.


#include <cstdio>
/**
* https://www.acmicpc.net/problem/10250
* BOJ 백준온라인져지 10250 ACM 호텔 풀이
*/
int main(){
int T,H,W,N,result;
scanf("%d", &T);
while(T--){
scanf("%d%d%d",&H,&W,&N);
W = 1;
while(N>H) W++, N-=H;
printf("%d%02d\n", N, W);
}
return 0;
}
view raw BOJ_10250.cpp hosted with ❤ by GitHub


저작자표시

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

BOJ 백준온라인져지 1475 방 번호 풀이  (0) 2017.11.13
BOJ 백준온라인져지 2775 부녀회장이 될테야 풀이  (0) 2017.11.12
BOJ 백준 1011 Fly me to the Alpha Centauri 풀이 Raw  (0) 2017.11.12
BOJ 2188 풀이 (이분매칭)  (0) 2017.11.08
BOJ 10803 풀이  (1) 2017.11.06

1 1

2 1 1

3 1 1 1

4 1 2 1

5 1 1 2 1

6 1 2 2 1

7 1 1 2 2 1


이동 거리는 이런식으로 된다.

idx    이동횟수

1         1

2        2

3        3

5        4

7        5


y에 이동해야 되는 거리를 넣어두고

pos에 현재 위치를 담았다.

처음에는 무조건 1을 이동해야 돼서 초기값이 1이다.

while loop을 돌때 i++/2를 해준 이유는 

9를 예로들면

1 2 3 2 1 인데

pos의 값이

1

while loop 시작

2

3

5

7

10

끝

이다.

i의 값을 구하면 5다.


결론적으로는

1 2 3 2 1

인것을

1 1 2 2 3 로 하는거다.

3을 예로들면

1 2 3 이 된다.

1 1 1 ㅇㅇ


끝.

저작자표시

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

BOJ 백준온라인져지 2775 부녀회장이 될테야 풀이  (0) 2017.11.12
BOJ 백준온라인져지 10250 ACM 호텔 풀이  (0) 2017.11.12
BOJ 2188 풀이 (이분매칭)  (0) 2017.11.08
BOJ 10803 풀이  (1) 2017.11.06
BOJ 10800 컬러볼 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 고등부 2번 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 초등부 4번)  (0) 2017.11.02

다른 블로그를 많이 참고했다.

import java.util.*;
import java.io.*;
/**
* BOJ 2188 축사 배정
*/
class Main {
private static boolean visited[];
private static int edges[][], N, M, B[];
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(" ");
N = Integer.parseInt(str1[0]);
M = Integer.parseInt(str1[1]);
edges = new int[N+1][M+1];
visited = new boolean[N+1];
B = new int[N+1];
for(int i = 1; i<=N; i++){
String str2[] = br.readLine().split(" ");
int length = Integer.parseInt(str2[0]);
Arrays.fill(edges[i], -1);
for(int j = 1; j<=length; j++){
edges[i][j] = Integer.parseInt(str2[j]);
}
}
int result = 0;
for(int i = 1; i<=N; i++){
Arrays.fill(visited, false);
if(dfs(i)) result++;
}
bw.write(String.valueOf(result));
bw.flush();
}
private static boolean dfs(int start){
visited[start] = true;
for(int i = 1; i<=M; i++){
if(edges[start][i] == -1) break;
int v = edges[start][i];
if(B[v] == 0 || (!visited[B[v]] && dfs(B[v]))){
B[v] = start;
return true;
}
}
return false;
}
}
view raw Main.java hosted with ❤ by GitHub


저작자표시

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

BOJ 백준온라인져지 10250 ACM 호텔 풀이  (0) 2017.11.12
BOJ 백준 1011 Fly me to the Alpha Centauri 풀이 Raw  (0) 2017.11.12
BOJ 10803 풀이  (1) 2017.11.06
BOJ 10800 컬러볼 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 고등부 2번 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 초등부 4번)  (0) 2017.11.02
BOJ 10797 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 초등부 1번)  (0) 2017.10.27

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

문제를 2가지 방법으로 풀었다.


첫 번째 방법은 노트를 없이 풀었는데, 문제를 잘 못 이해해서 시간초과가 났고,

두 번째 풀이는 메모이제이션을 이용해 코드를 작성했다.


import java.io.*;
import java.util.*;
/**
* BOJ 2591 숫자카드
* https://gist.github.com/KSH-code/620b7c790d2e820c56c984b1ae2addca
* 주석처리가 된 곳은 Memorization을 사용하지 않은 부분
* 또는
* 노트가 없어서 걍 풀이 흔적
*/
class Main{
// private static int result = 0; private static char ss[];
private static int length;
private static String s;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
s = br.readLine();
length = s.length();
int slicedNumber[] = new int[100];
for(int i = 0; i<s.length(); i++){
slicedNumber[i] = s.charAt(i) - 48;
}
// 2 7 1 2 3
// 1 1
// 1 1 2 3 5 6
int dp[] = new int[100];
dp[0] = 1;
dp[1] = 1;
for(int i = 1; i<length+1; i++){
if(slicedNumber[i-1] == 0){
if(slicedNumber[i-2] > 0 && slicedNumber[i-2]*10 + slicedNumber[i-1] <= 36){
dp[i] = dp[i-2];
}else{
System.out.println(0);
return;
}
}else{
dp[i] = dp[i - 1];
if(i-2>=0){
if(slicedNumber[i-2] > 0 && slicedNumber[i-2]*10 + slicedNumber[i-1] <= 36){
dp[i] = dp[i-2] + dp[i-1];
}
}
}
}
System.out.println(dp[s.length()]);
// ss = s.toCharArray();
// gogo("", 0);
// System.out.println(result);
}
// private static void gogo(String t, int idx){
// if(t.length() >= length){
// if(t.length() == length)
// result++;
// return;
// }else{
// String Stemp = String.valueOf(ss[idx]);
// if(idx + 2 <= length){
// String Stemp2 = Stemp + String.valueOf(ss[idx + 1]);
// if(Integer.parseInt(Stemp2) <= 36 && ss[idx] != '0'){
// gogo(t + Stemp2, idx+2);
// }
// }
// if(ss[idx] != '0'){
// gogo(t + Stemp, idx+1);
// }
// }
// }
}
view raw Main.java hosted with ❤ by GitHub
저작자표시

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

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
BOJ 2590 색종이 풀이(Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 4번 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 중등부 2번)  (0) 2017.10.25
BOJ 2042 구간 합 구하기 풀이  (0) 2017.10.24
BOJ 2589 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 3번)  (0) 2017.10.23

1보다는 2를 먼저 채우는 방식으로 짰다.

import java.io.*;
import java.util.*;
/**
* BOJ 2590 색종이
* https://gist.github.com/KSH-code/1003dec637b9281c88ef3f2fb162f0c5
*/
class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int d[] = new int[7];
for(int i = 1; i<=6; i++){
d[i] = Integer.parseInt(br.readLine());
}
int five = d[5] * 11;
int four = d[4] * 5;
int panel = d[6] + d[5] + d[4];
d[1] -= five;
d[2] -= four;
if(d[1] > 0 && d[2] < 0){
d[1] += d[2] * 4;
}
panel += d[3] / 4;
int three;
if((three = (d[3] % 4)) > 0){
panel++;
d[2] = Math.max(d[2], 0);
if(d[2] >= 0){
d[2] -= 5 - (three-1) * 2;
d[1] += d[2] * 4;
d[1] -= 8 - three;
}
}
if(d[2] > 0){
panel += d[2] / 9;
int two;
if((two = (d[2] % 9)) > 0){
panel++;
int ableone = -4 * two + 36;
d[1] -= ableone;
}
}
while(d[1] > 0){
panel++;
d[1] -= 36;
}
System.out.println(panel);
}
}
view raw Main.java hosted with ❤ by GitHub


저작자표시

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

BOJ 1907 풀이 (Olympiad > Croatian Highschool Competitions in Informatics > 2005 > Regional Competition - Juniors 3번)  (0) 2017.10.26
BOJ 2951 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 5번 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 중등부 3번)  (0) 2017.10.25
BOJ 2042 구간 합 구하기 풀이  (0) 2017.10.24
BOJ 2589 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 3번)  (0) 2017.10.23
BOJ 12852 1로 만들기 2 풀이  (0) 2017.10.20

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

알고리즘 스터디 자료를 준비중에 ADT라는 용어를 접했다.


ADT는 Abstract-Data-Type이다.

말 그대로 추상 자료형.


Wallet이라는 자료형을 선언했다.


그 Wallet을 기반으로 연산의 종류가 있을것이다.

그것도 자료형 정의의 일부다.


자료의 ADT는

기능들이다.

기능들 말고도 구조체의 정의도 넣을 수 있다.

근데 ADT에는 필요한 정보들만 넣는것이 좋다.


리스트

  • 순차 리스트
  • 연결 리스트

둘의 ADT가 같을 수 있다.


ADT에 표준은 없다.

생각은 모두 자유롭게 할 수있고, 그것을 코드로 옮길 수 있다.


위 둘의 리스트의 공통점은


선형구조다.




저작자표시

'이전 글 > 2017-10-13 이전 글' 카테고리의 다른 글

폼 입력 바인딩  (0) 2017.07.19
LinkedList  (0) 2017.07.16
이벤트 핸들링  (0) 2017.07.13
ejs, jade를 사용해봤다.  (0) 2017.07.12
리스트 렌더링  (0) 2017.07.11

+ Recent posts

티스토리툴바