문제 설명

1. N * N 칸의 체스판이 있을 때, 퀸이 서로 공격 못하는 상황을 만들어라(퀸으 개수는 N 개)

풀이

백트랙킹을 사용해서 풀었다.
1. col 이라는 배열은 index 열의 값이 x 번 째 행에 존재한다는 것이다.
2. 속도를 더 빠르게 하려면 대각선과 이전에 작업했던 것 들을 저장하는 배열이 있으면 될 것 이다.

코드

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/9663
* BOJ 백준온라인져지 9663 N-Queen 풀이
*/
public class Main {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static int result = 0, N;
private static int col[];
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
col = new int[N + 1];
// (1, 1) (2, 1)
// (1, 2) (2, 2)
for (int i = 1; i <= N; i++) {
col[1] = i; // 첫 번째 가로 칸의 i 번 째 세로칸을 채운다. (1, i)
dfs(1);
}
bw.write(String.valueOf(result));
bw.flush();
}
private static void dfs (int x) {
if (x == N) {
result++;
} else {
for (int i = 1; i <= N; i++) {
int temp = x + 1;
col[temp] = i;
for (int j = 1; j <= x; j++) {
if (col[j] == i || Math.abs(j - temp) == Math.abs(col[j] - i)) { // 대각선, 같은행 확인
col[temp] = 0;
break;
}
}
if (col[temp] == i) dfs(temp);
}
}
col[x] = 0;
}
}
view raw Main.java hosted with ❤ by GitHub

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1 

8

예제 출력 1 

92


저작자표시

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

BOJ 백준온라인져지 1550 16진수 풀이  (0) 2018.06.21
BOJ 백준온라인져지 11724 연결 요소의 개수 풀이  (0) 2018.06.21
BOJ 백준온라인져지 1699 제곱수의 합 풀이  (0) 2018.06.19
BOJ 백준온라인져지 2583 영역 구하기 풀이  (0) 2018.06.19
BOJ 백준온라인져지 2523 별찍기 - 13 풀이  (0) 2018.06.18

문제 설명 

1. 어떤 수 N 이 있을 때, 그 N 을 만들 수 있는 제곱수들의 합의 최소 개수를 구하면 되는 문제다.

풀이

1. dp 로 풀었다. dp 완전탐색
dp[i] = 답
답 = 1 or dp[i - j * j] + dp[j * j] (1 <= j * j <= i)

증명

1. dp[2] = dp[1] + dp[1] 이다.
2. dp[3] = dp [1] + dp[2] 이다.
결론적으로는 각 단계에서 구해놨던 최적해를 이용해서 우리가 구하고자 하는 최적해를 구할 수 있다는 것이다.
만약 N 이 10이라고 가정하면 답은 2 일 것이다.
그런데 구하는 과정이 어떻게되냐?
dp[i - j * j] + dp[j * j] (1 <= j * j <= i) j 를 증가시키면서 값을 업데이트 해주는데 저 조건에 해당하는 값은 제일 높은 값은 j = 3 일 때 이다.
j = 3 일 때 dp[9] + dp[1] 이 되므로 i 가 N 까지 도달하면서 이미 구해놨던 답을 기반으로 구할 수 있다. dp[9] 는 3 * 3 이므로 1 로 변경한다.

코드

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/1699
* BOJ 백준온라인져지 1699 제곱수의 합 풀이
*/
public class Main {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int dp[] = new int[N + 2];
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; j++) {
if (i == j * j) {
dp[i] = 1;
break;
}
dp[i] = Math.min(dp[i - j * j] + dp[j * j], dp[i]);
}
}
bw.write(String.valueOf(dp[N]));
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

예제 입력 1 

7

예제 출력 1 

4

출처

ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2007 E번


저작자표시

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

BOJ 백준온라인져지 11724 연결 요소의 개수 풀이  (0) 2018.06.21
BOJ 백준온라인져지 9663 N-Queen 풀이  (0) 2018.06.20
BOJ 백준온라인져지 2583 영역 구하기 풀이  (0) 2018.06.19
BOJ 백준온라인져지 2523 별찍기 - 13 풀이  (0) 2018.06.18
BOJ 백준온라인져지 1032 명령 프롬프트 풀이  (0) 2018.06.16

문제 설명

1. 색칠되지 않은 영역의 개수와 넓이를 구하면 되는 문제다.

풀이

처음에는 색칠된 영역에서 나눠진 그룹별로 넓이를 구하는건줄 알았는데 색칠되지 않은 영역을 구하는 문제였다.
색칠된 영역은 영역끼리 구분될 필요가 없으므로 true 로 설정했고, false 인것끼리 dfs 를 했다.
bfs 를 사용하지 않은 이유
1. dfs 로 하면 영역별로 나누는게 쉽다. (재귀함수기 때문에 한 번 확인하는 영역은 끝을 봄)
2. dfs 안에 bfs 를 넣을 수 있었는데 귀찮았다.
PriorityQueue (max-heap) 를 사용한 이유
1. 원래는 LinkedList 를 사용하려 했었는데 정렬을 해야되서 귀찮았다.
2. 하나씩 앞에서 꺼내쓰는게 queue 랑 맞다고 생각했기 때문이다.

결론적으로 풀이 방법은
1. dfs 를 이용해서 모든 구역을 확인하고 각 영역별로 넓이를 큐에 담아줬다.
2. 큐에 담겨진 데이터의 개수를 모드 출력하고 데이터를 순차적으로 출력했다.

코드

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/2583
* BOJ 백준온라인져지 2583 영역 구하기 풀이
*/
public class Main {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static PriorityQueue<Integer> result = new PriorityQueue<>();
private static int N, M;
private static boolean map[][], visited[][];
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
map = new boolean[N][M];
visited = new boolean[N][M];
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
for (int j = x1; j < x2; j++) {
for (int k = y1; k < y2; k++) {
map[k][j] = true;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (!map[i][j] && !visited[i][j]) result.offer(dfs(i, j));
}
}
bw.write(String.valueOf(result.size()));
bw.write("\n");
while (!result.isEmpty()) {
bw.write(String.valueOf(result.poll()));
bw.write(" ");
}
bw.flush();
}
private static int xxxx[] = { -1, 0, 1, 0 };
private static int yyyy[] = { 0, 1, 0, -1 };
private static int dfs (int x, int y) {
visited[x][y] = true;
int result = 1;
for (int i = 0; i < 4; i++) {
int curX = x + xxxx[i];
int curY = y + yyyy[i];
if (curX < 0 || curY < 0 || curX >= N || curY >= M || visited[curX][curY] || map[curX][curY]) continue;
result += dfs(curX, curY);
}
return result;
}
}
view raw Main.java hosted with ❤ by GitHub

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

예제 입력 1 

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

예제 출력 1 

3
1 7 13

출처

Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 고등부 2번


저작자표시

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

BOJ 백준온라인져지 9663 N-Queen 풀이  (0) 2018.06.20
BOJ 백준온라인져지 1699 제곱수의 합 풀이  (0) 2018.06.19
BOJ 백준온라인져지 2523 별찍기 - 13 풀이  (0) 2018.06.18
BOJ 백준온라인져지 1032 명령 프롬프트 풀이  (0) 2018.06.16
BOJ 백준온라인져지 5543 상근날드 풀이  (0) 2018.06.16

조금 쉽게 풀어보려 했지만 실패

코드

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/2523
* BOJ 백준온라인져지 2523 별찍기 - 13 풀이
*/
public class Main {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for (int j = 1; j <= 2 * N - 1; j++) {
for (int i = 1; i <= (j < N ? j : 2 * N - j); i++) {
bw.write("*");
}
bw.write("\n");
}
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

  예제를 보고 별찍는 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

  첫째 줄에 N (1<=N<=100)이 주어진다.

출력

  첫째 줄부터 2*N-1번째 줄 까지 차례대로 별을 출력한다.

예제 입력 1 

3

예제 출력 1 

*
**
***
**
*


저작자표시

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

BOJ 백준온라인져지 1699 제곱수의 합 풀이  (0) 2018.06.19
BOJ 백준온라인져지 2583 영역 구하기 풀이  (0) 2018.06.19
BOJ 백준온라인져지 1032 명령 프롬프트 풀이  (0) 2018.06.16
BOJ 백준온라인져지 5543 상근날드 풀이  (0) 2018.06.16
BOJ 백준온라인져지 14888 연산자 끼워넣기 풀이  (0) 2018.06.16

문제 설명

1. 문자열이 입력된게 모두 맞으면 그대로 출력하면 되고 다른 부분은 ? 로 출력하면 된다.

풀이

1. 문자열의 길이는 모두 같으므로 0 번 째를 기준으로 비교한다. (하나라도 다른게 보인다면 그 부분은 다르므로 ? 처리)
2. 다른게 없으면 그대로 출력

코드

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/1032
* BOJ 백준온라인져지 1032 명령 프롬프트 풀이
*/
public class Main {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String str1[] = new String[N];
for (int i = 0; i < N; i++) str1[i] = br.readLine();
for (int i = 0; i < str1[0].length(); i++) {
int isNotEqual = 0;
for (int j = 1; j < N; j++) isNotEqual |= str1[0].charAt(i) - str1[j].charAt(i);
if (isNotEqual != 0) bw.write("?");
else bw.write(str1[0].charAt(i));
}
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이 때 원하는 파일을 찾으려면 다음과 같이 하면 된다.

dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. "dir 패턴"과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이 때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다.

이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제이다. 패턴에는 알파벳과 "." 그리고 "?"만 넣을 수 있다. 가능하면 ?을 적게 써야 한다. 그 디렉토리에는 검색 결과에 나온 파일만 있다고 가정하고, 파일 이름의 길이는 모두 같다.

입력

첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 알파벳과 "." 그리고 "?"로만 이루어져 있다.

출력

첫째줄에 패턴을 출력하면 된다.

예제 입력 1 

3
config.sys
config.inf
configures

예제 출력 1 

config????


저작자표시

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

BOJ 백준온라인져지 2583 영역 구하기 풀이  (0) 2018.06.19
BOJ 백준온라인져지 2523 별찍기 - 13 풀이  (0) 2018.06.18
BOJ 백준온라인져지 5543 상근날드 풀이  (0) 2018.06.16
BOJ 백준온라인져지 14888 연산자 끼워넣기 풀이  (0) 2018.06.16
BOJ 백준온라인져지 2805 나무 자르기 풀이  (0) 2018.06.16
import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/5543
* BOJ 백준온라인져지 5543 상근날드 풀이
*/
public class Main {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int burger = Integer.MAX_VALUE;
for (int i = 0; i < 3; i++) burger = Math.min(burger, Integer.parseInt(br.readLine()));
int drink = Integer.MAX_VALUE;
for (int i = 0; i < 2; i++) drink = Math.min(drink, Integer.parseInt(br.readLine()));
bw.write(String.valueOf(burger + drink - 50));
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub


문제

상근날드에서 가장 잘 팔리는 메뉴는 세트 메뉴이다. 주문할 때, 자신이 원하는 햄버거와 음료를 하나씩 골라, 세트로 구매하면, 가격의 합계에서 50원을 뺀 가격이 세트 메뉴의 가격이 된다.

햄버거는 총 3종류 상덕버거, 중덕버거, 하덕버거가 있고, 음료는 콜라와 사이다 두 종류가 있다.

햄버거와 음료의 가격이 주어졌을 때, 가장 싼 세트 메뉴의 가격을 출력하는 프로그램을 작성하시오.

입력

입력은 총 다섯 줄이다. 첫째 줄에는 상덕버거, 둘째 줄에는 중덕버거, 셋째 줄에는 하덕버거의 가격이 주어진다. 넷째 줄에는 콜라의 가격, 다섯째 줄에는 사이다의 가격이 주어진다. 모든 가격은 100원 이상, 2000원 이하이다.

출력

첫째 줄에 가장 싼 세트 메뉴의 가격을 출력한다.

예제 입력 1 

800
700
900
198
330

예제 출력 1 

848

출처

Olympiad > 일본정보올림피아드 예선 > JOI 2012 예선 1번


저작자표시

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

BOJ 백준온라인져지 2523 별찍기 - 13 풀이  (0) 2018.06.18
BOJ 백준온라인져지 1032 명령 프롬프트 풀이  (0) 2018.06.16
BOJ 백준온라인져지 14888 연산자 끼워넣기 풀이  (0) 2018.06.16
BOJ 백준온라인져지 2805 나무 자르기 풀이  (0) 2018.06.16
BOJ 백준온라인져지 1309 동물원 풀이  (0) 2018.06.15

문제 설명

1. 연산자 우선순위는 없고 순서대로 연산하는거다. (앞에서부터)
2. 잘 배치해서 최대값, 최소값을 구해주면 된다.

풀이

1. dfs (브루트포스) 를 사용해서 완전 탐색을 해본다.
2. 모든 경우의 수를 대입하게 되면 무조건 답을 구할 수 밖에 없다.

코드

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/14888
* BOJ 백준온라인져지 14888 연산자 끼워넣기 풀이
*/
public class Main {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static int arr[];
private static int operators[] = new int[4];
private static int max = Integer.MIN_VALUE;
private static int min = Integer.MAX_VALUE;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < 4; i++) operators[i] = Integer.parseInt(st.nextToken());
dfs(arr[0], 1);
bw.write(String.valueOf(max));
bw.write("\n");
bw.write(String.valueOf(min));
bw.flush();
}
private static void dfs (int sum, int idx) {
if (idx == arr.length) {
max = Math.max(sum, max);
min = Math.min(sum, min);
}
for (int i = 0; i < 4; i++) {
if (operators[i] > 0) {
operators[i]--;
switch (i) {
case 0: dfs(sum + arr[idx], idx + 1); break;
case 1: dfs(sum - arr[idx], idx + 1); break;
case 2: dfs(sum * arr[idx], idx + 1); break;
case 3: dfs(sum / arr[idx], idx + 1); break;
}
operators[i]++;
}
}
}
}
view raw Main.java hosted with ❤ by GitHub

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이 때, 주어진 수의 순서를 바꾸면 안된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

  • 1+2+3-4×5÷6
  • 1÷2+3+4-5×6
  • 1+2÷3×4-5+6
  • 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

  • 1+2+3-4×5÷6 = 1
  • 1÷2+3+4-5×6 = 12
  • 1+2÷3×4-5+6 = 5
  • 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

출력

첫째 줄에 만들 수 있는 식의 결과의 최대값을, 둘째 줄에는 최소값을 출력한다. 최대값과 최소값은 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서 부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

예제 입력 1 

2
5 6
0 0 1 0

예제 출력 1 

30
30

예제 입력 2 

3
3 4 5
1 0 1 0

예제 출력 2 

35
17

예제 입력 3 

6
1 2 3 4 5 6
2 1 1 1

예제 출력 3 

54
-24

힌트

세 번째 예제의 경우에 다음과 같은 식이 최대값/최소값이 나온다.

  • 최대값: 1-2÷3+4+5×6
  • 최소값: 1+2+3÷4-5×6


저작자표시

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

BOJ 백준온라인져지 1032 명령 프롬프트 풀이  (0) 2018.06.16
BOJ 백준온라인져지 5543 상근날드 풀이  (0) 2018.06.16
BOJ 백준온라인져지 2805 나무 자르기 풀이  (0) 2018.06.16
BOJ 백준온라인져지 1309 동물원 풀이  (0) 2018.06.15
BOJ 백준온라인져지 2003 수들의 합 2 풀이  (0) 2018.06.15

문제 설명

1. 자른 나무의 길이가 M 이상일 때 H 의 최대값을 구하시오

풀이

1. 나무의 최대 길이를 구해서 이분 탐색을 돌린다.

증명

1. 이분 탐색으로 남은 길이를 계속 구하면서 길이가 더 작다면 right 의 끝을 중간 - 1 로 해준다. 그 다음 이분 탐색을 반복하면 된다.
2. 아니라면 반대로 쭉 돌린다.

코드

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/2805
* BOJ 백준온라인져지 2805 나무 자르기 풀이
*/
public class Main {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int arr[] = new int[N];
st = new StringTokenizer(br.readLine());
int maxHeight = 0;
for (int i = 0; i < N; i++) maxHeight = Math.max(maxHeight, arr[i] = Integer.parseInt(st.nextToken()));
int l = 1;
int r = maxHeight;
int m = (l + r) / 2;
while (l <= r) {
long sum = 0;
for (int i = 0; i < N; i++) sum += Math.max(0, arr[i] - m);
if (sum < M) r = m - 1;
else l = m + 1;
m = (l + r) / 2;
}
bw.write(String.valueOf(r));
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다)

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이 때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최대값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 넘기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최대값을 출력한다.

예제 입력 1 

4 7
20 15 10 17

예제 출력 1 

15

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #5 2번


저작자표시

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

BOJ 백준온라인져지 5543 상근날드 풀이  (0) 2018.06.16
BOJ 백준온라인져지 14888 연산자 끼워넣기 풀이  (0) 2018.06.16
BOJ 백준온라인져지 1309 동물원 풀이  (0) 2018.06.15
BOJ 백준온라인져지 2003 수들의 합 2 풀이  (0) 2018.06.15
BOJ 백준온라인져지 2133 타일 채우기 풀이  (0) 2018.06.14

문제 설명

1. 사자는 상하좌우로 겹칠 수 없다.
2. 없는 경우의 수도 카운트를 센다.

풀이

1. dp 를 이용해 풀었다.
2. i 번째 칸에 사자가 없는 경우
3. i 번째 칸에 사자가 왼쪽에 있는 경우
4. i 번째 칸에 사자가 오른쪽에 있는 경우
5. 위의 3 가지를 이용해서 풀었다.

증명

1. 1 번째 에서는 경우의 수가 3가지다.(항상)
2. i (i >= 2) 번째 에는 i - 1 번 째에 저장된 값을 이용해서 구할 수 있다. 예를 들어 [i][0] 을 구한다 하면 이전거에서 다 가능하기 때문에 [i-1][0~2] 를 다 더해줄 수 있다. 이런 방법을 사용하면
3. i 를 증가시키면서 답을 구할 수 있다.

코드

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/1309
* BOJ 백준온라인져지 1309 동물원 풀이
*/
public class Main {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int dp[][] = new int[N + 1][3];
dp[1][0] = dp[1][1] = dp[1][2] = 1;
for (int i = 2; i <= N; i++) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
}
bw.write(String.valueOf((dp[N][0] + dp[N][1] + dp[N][2]) % 9901));
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

예제 입력 1 

4

예제 출력 1 

41


저작자표시

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

BOJ 백준온라인져지 14888 연산자 끼워넣기 풀이  (0) 2018.06.16
BOJ 백준온라인져지 2805 나무 자르기 풀이  (0) 2018.06.16
BOJ 백준온라인져지 2003 수들의 합 2 풀이  (0) 2018.06.15
BOJ 백준온라인져지 2133 타일 채우기 풀이  (0) 2018.06.14
BOJ 백준온라인져지 2902 KMP는 왜 KMP일까? 풀이  (0) 2018.06.14

문제 설명

1. 연속된 부분집합 수열에서의 합이 M 이 되면 된다.

풀이

1. 투 포인터를 사용했다.

증명

1. left right 가 인덱스를 저장해서 영역을 지정한다.
2. sum 이 더 크면 left 가 오른쪽으로 한 칸 오면서 빼고
3. 더 작으면 right 가 오른쪽으로 한 칸 가면서 더한다.
4. 반복하면 O(N)

코드

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/2003
* BOJ 백준온라인져지 2003 수들의 합 2 풀이
*/
public class Main {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int arr[] = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
int sum = 0;
int l = 0, r = 0;
int result = 0;
while (true) {
if (sum >= M) sum -= arr[l++];
else if (r == N) break;
else sum += arr[r++];
if (sum == M) result++;
}
bw.write(String.valueOf(result));
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1 

4 2
1 1 1 1

예제 출력 1 

3

예제 입력 2 

10 5
1 2 3 4 2 5 3 1 1 2

예제 출력 2 

3


저작자표시

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

BOJ 백준온라인져지 2805 나무 자르기 풀이  (0) 2018.06.16
BOJ 백준온라인져지 1309 동물원 풀이  (0) 2018.06.15
BOJ 백준온라인져지 2133 타일 채우기 풀이  (0) 2018.06.14
BOJ 백준온라인져지 2902 KMP는 왜 KMP일까? 풀이  (0) 2018.06.14
BOJ 백준온라인져지 2522 별 찍기 - 12 풀이  (0) 2018.06.13

+ Recent posts

티스토리툴바