1. 문제 = 답

2. 오버플로 조심

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/13699
* BOJ 백준온라인져지 13699 점화식 풀이
*/
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());
long t[] = new long[N + 1];
t[0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < i; j++) {
t[i] += t[j] * t[i - 1 - j];
}
}
bw.write(String.valueOf(t[N]));
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:

  • t(0)=1
  • t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)

이 정의에 따르면,

  • t(1)=t(0)*t(0)=1
  • t(2)=t(0)*t(1)+t(1)*t(0)=2
  • t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5
  • ...

주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다.

출력

첫째 줄에 t(n)을 출력한다.

예제 입력 1 

3

예제 출력 1 

5

예제 입력 2 

25

예제 출력 2 

4861946401452

힌트

출처

University > 홍익대학교 > 홍익대학교 프로그래밍 경진대회 2016 B번


저작자표시

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

BOJ 백준온라인져지 2470 두 용액 풀이  (0) 2018.05.04
BOJ 백준온라인져지 5585 거스름돈 풀이  (0) 2018.05.03
BOJ 백준온라인져지 2331 반복수열 풀이  (0) 2018.05.02
BOJ 백준온라인져지 1015 수열 정렬 풀이  (0) 2018.05.01
BOJ 백준온라인져지 11945 뜨거운 붕어빵 풀이  (0) 2018.04.30

1. 문자열을 뒤집어서 출력하는 문제

2. 간단하게 구현완료!

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/11945
* BOJ 백준온라인져지 11945 뜨거운 붕어빵 풀이
*/
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));
String str1[] = br.readLine().split(" ");
int N = Integer.parseInt(str1[0]);
int M = Integer.parseInt(str1[1]);
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++) {
bw.write(str.charAt(M - j - 1));
}
bw.write("\n");
}
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

고려대학교에 입학한 새내기 호돌이는 안암역을 지나다가 한 붕어빵 장수를 만났어요.

“안녕, 안녕, 안녕하십니까, 아저씨! 붕어빵 두 개 주세요.”

“안녕을 세 번 외쳤으니 붕어빵 세 개!”

붕어빵 두 개의 값을 내고 세 개를 받은 호돌이는 기분이 좋았어요. 호돌이가 붕어빵 하나를 꺼내어 한 입 물었는데…. 너무 뜨거워서 그만 붕어빵을 떨어뜨리고 말았어요ㅠㅠ

붕어빵은 자유 낙하운동을 하면서 땅에 떨어졌는데 신기하게도 좌우가 뒤집힌 모양으로 착지했답니다. 호돌이가 붕어빵을 한 입 물기 전의 모양이 입력으로 주어지면, 땅에 떨어졌을 때에는 어떤 모양일지 출력하세요.

입력

첫째 줄에는 두 개의 정수 N과 M(0≤N,M≤10)이 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 붕어빵의 모양이 주어집니다. 각 행에는 공백을 나타내는 ‘0‘ 또는 붕어빵을 나타내는 ‘1’이 총 M개 주어집니다. 

출력

입력으로 주어진 붕어빵이 좌우로 뒤집힌 모양을 출력하세요.

예제 입력 1 

5 7
0010000
0111010
1111111
0111010
0010000

예제 출력 1 

0000100
0101110
1111111
0101110
0000100

힌트

입력으로 주어지는 각 행을 반전시켜서 출력하면 됩니다. 입력의 1행 1열은 출력의 1행 M열로, 입력의 1행 2열은 출력의 1행 M-1열로 … 입력의 1행 M열은 출력의 1행 1열로 … 입력의 N행 M열은 출력의 N행 1열로 출력하세요.

출처

University > 고려대학교 > 2016 고려대학교 신입생 프로그래밍 경시대회 D번


저작자표시

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

BOJ 백준온라인져지 2331 반복수열 풀이  (0) 2018.05.02
BOJ 백준온라인져지 1015 수열 정렬 풀이  (0) 2018.05.01
BOJ 백준온라인져지 11943 파일 옮기기 풀이  (0) 2018.04.30
BOJ 백준온라인져지 11944 NN 풀이  (0) 2018.04.27
BOJ 백준온라인져지 1194 달이 차오른다, 가자. 풀이  (0) 2018.04.26

1. 경우의 수는 2개

2. 2개다 해보면됨 (완전탐색)

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/11943
* BOJ 백준온라인져지 11943 파일 옮기기 풀이
*/
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));
String str1[] = br.readLine().split(" ");
String str2[] = br.readLine().split(" ");
int A1 = Integer.parseInt(str1[0]);
int A2 = Integer.parseInt(str2[0]);
int B1 = Integer.parseInt(str1[1]);
int B2 = Integer.parseInt(str2[1]);
bw.write(String.valueOf(Math.min(A1 + B2, A2 + B1)));
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

두 개의 바구니에 사과와 오렌지가 있다. 첫 번째 바구니에는 사과 A개와 오렌지 B개가 있으며 두 번째 바구니에는 사과 C개와 오렌지 D개가 있다.

당신은 한 바구니에 있는 과일 하나를 집어서 다른 바구니로 옮길 수 있다. 이런 식으로 과일을 옮길 때, 한 바구니에는 사과만 있게 하고 다른 쪽에는 오렌지만 있게 하려고 한다.

앞서 말한 조건을 만족하도록 과일을 옮길 때, 과일을 옮기는 최소 횟수를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 첫 번째 바구니에 있는 사과와 오렌지의 수 A, B가 주어진다. (0 ≤ A, B ≤ 1,000)

두 번째 줄에는 두 번째 바구니에 있는 사과와 오렌지의 수 C, D가 주어진다. (0 ≤ C, D ≤ 1,000)

출력

사과와 오렌지를 옮기는 최소 횟수를 출력한다.


저작자표시

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

BOJ 백준온라인져지 1015 수열 정렬 풀이  (0) 2018.05.01
BOJ 백준온라인져지 11945 뜨거운 붕어빵 풀이  (0) 2018.04.30
BOJ 백준온라인져지 11944 NN 풀이  (0) 2018.04.27
BOJ 백준온라인져지 1194 달이 차오른다, 가자. 풀이  (0) 2018.04.26
BOJ 백준온라인져지 2559 수열 풀이  (0) 2018.04.25

1. 그냥 단순하게 M 번 돌리면 된다.

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/11944
* BOJ 백준온라인져지 11944 NN 풀이
*/
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));
String str1[] = br.readLine().split(" ");
int N = Integer.parseInt(str1[0]);
int M = Integer.parseInt(str1[1]);
for (int i = 0; i < N; i++) {
for (int j = 0; j < str1[0].length(); j++) {
if (M == 0) {
i = N;
break;
}
bw.write(str1[0].charAt(j));
M--;
}
}
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

문제는 매우 간단하다. N을 N번 출력하는 프로그램을 작성하여라. 다만, 답이 길어지는 경우 답의 앞 M자리만 출력한다.

입력

첫 번째 줄에는 N, M이 주어진다. (1 ≤ N, M ≤ 2016)

출력

N을 N번 출력한다. 만약 답이 길어지면 답의 앞 M자리를 출력한다.


저작자표시

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

BOJ 백준온라인져지 11945 뜨거운 붕어빵 풀이  (0) 2018.04.30
BOJ 백준온라인져지 11943 파일 옮기기 풀이  (0) 2018.04.30
BOJ 백준온라인져지 1194 달이 차오른다, 가자. 풀이  (0) 2018.04.26
BOJ 백준온라인져지 2559 수열 풀이  (0) 2018.04.25
BOJ 백준온라인져지 12845 모두의 마블 풀이  (0) 2018.04.25

1. 레벨의 변화가 없어서 다 더하면된다.

2. O(N)

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/12845
* BOJ 백준온라인져지 12845 모두의 마블 풀이
*/
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));
br.readLine();
String str1[] = br.readLine().split(" ");
int max = 0;
int maxIndex = 0;
int result = 0;
for (int i = 0; i < str1.length; i++) {
int level = Integer.parseInt(str1[i]);
if (max < level) {
max = level;
maxIndex = i;
}
result += level;
}
result += max * (str1.length - 2);
bw.write(String.valueOf(result));
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블 일 것이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여 했다.

이번 이벤트는 다음과 같다. 순서가 매겨진 여러 장의 카드가 있다. 각각의 카드는 저마다 레벨이 있다.

카드 A에 카드 B를 덧붙일 수 있다.  이 때 붙이는 조건은 다음과 같다.

  1. 두 카드는 인접한 카드여야 한다.
  2. 업그레이드 된 카드 A의 레벨은 변하지 않는다.

카드 합성을 할 때 마다 두 카드 레벨의 합 만큼 골드를 받는다.

영관이가 골드를 최대한 많이 받을 수 있게 여러분이 도와주자.

예를 들어, c1,c2,c3로 연속된 카드 3개가 있고 각각 레벨이 40,30,30 이라고 하자.

이 카드들을 합치는 과정에서, 먼저 c3 에 c2 를 합쳐 임시 카드 x1 를 만든다. x1의 레벨은 30이고 획득 골드는 60이다. 그 다음엔 c1 에 x1 을 합쳐 카드 x2 를 만들면 레벨이 40 이고 70만큼의 골드를 획득 할 수 있다. 이 때, 영관이가 획득한 골드는 70+60 = 130이다.

다른 방법으로 c1에 c2를 덧 붙인 카드 x1을 만들면, x1의 레벨은 40이고 획득 골드는 70이다.

x1에 c3를 덧 붙인 카드 x2의 레벨은 40이고 획득 골드는 70이다. 이 때, 영관이가 획득한 골드는 70 + 70 = 140 이다. 이외에 더 많은 골드를 받는 방법이 없으므로 140이 획득 할 수 있는 최대 골드이다.

입력

카드의 개수 n (0 < n ≤ 1,000)이 주어진다.

다음 줄에 각각 카드의 레벨 Li가 순서대로 주어진다. (0 < Li ≤ 100,000)

출력

영관이가 받을 수 있는 골드의 최대 값을 출력한다.


저작자표시

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

BOJ 백준온라인져지 11944 NN 풀이  (0) 2018.04.27
BOJ 백준온라인져지 1194 달이 차오른다, 가자. 풀이  (0) 2018.04.26
BOJ 백준온라인져지 2559 수열 풀이  (0) 2018.04.25
BOJ 백준온라인져지 12780 원피스 풀이  (0) 2018.04.24
BOJ 백준온라인져지 5671 호텔 방 번호 풀이  (0) 2018.04.23

1. 문자열 검색이라길래 KMP 를 바로 떠올렸다.

2. 공부하기 싫어서 잔머리를 쥐어 짜내다가 입력 제한값을 봤다.

3. 그냥 H 의 모든 문자를 N 번씩 봐도 문제가 없겠잖아? 하고 코드를 작성했다.

4. 런타임에러 띠용?

5. 알고보니까 charAt 은 length 값 이상이 될 수 없다.

6. 이것도 쉬운문제였다.

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/12780
* BOJ 백준온라인져지 12780 원피스 풀이
*/
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));
String str1 = br.readLine();
String str2 = br.readLine();
int cnt = 0;
for (int i = 0; i < str1.length(); i++) {
boolean no = false;
for (int j = 0; j < str2.length(); j++) {
if (i + j >= str1.length() || str1.charAt(i + j) != str2.charAt(j)) {
no = true;
break;
}
}
if (!no) cnt++;
}
bw.write(String.valueOf(cnt));
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

바야흐로 지금은 대해적 시대, 밀짚모자 해적단의 선장 교정이는 어린 시절 우연히 잊지 못할 한 마디를 들었다. 그것은 바로 해적 왕 골.D.상윤이 자신이 모은 모든 보물인 원피스를 위대한 항로에 놓고 왔다는 것이었다. 원피스를 가진 자는 이 세상을 가질 수 있다는 매혹적인 얘기였다.

모두들 말도 안 된다고 고개를 저었지만 교정이는 동료를 모아 원피스를 찾아 여행을 떠났다. 하늘섬을 지나 어인섬도 지나고 사황을 무너뜨린 뒤 교정이와 동료들은 결국 원피스의 위치가 적힌 결정적인 단서를 찾아냈다. 이 단서는 한 눈에 봐서는 해독이 어려웠다. 왜냐하면 여기에는 그저 알파벳 대문자들이 연속해서 적혀있었기 때문이다.

하지만 천재적인 두뇌를 가진 교정이의 동료이자 해적단의 항해사 진아는 단번에 이 단서에 어떤 특정 문자열이 여러 번 등장한다는 것을 직감했다.

이 특정 문자열이 어떤 문자열인지는 잘 알 수 없었던 진아는 자신이 생각한 모든 문자열이 이 단서에서 총 몇 번 등장하는지 알아보기로 했다. 아마도 가장 많이 등장한 문자열이 원피스의 위치를 알려줄 것이라고 생각했기 때문이다.

진아는 밀짚모자 해적단의 프로그래밍 담당인 당신에게 도움을 요청했다. 단서 전체에 진아가 원하는 문자열이 몇 번 등장하는지 알아내는 프로그램을 작성하라.

입력

입력의 첫 줄에는 해적단이 획득한 단서의 문자열 H가 주어진다.(0 < |H| ≤ 100,000)

입력의 두 번째 줄에는 진아가 H에서 등장 횟수를 알고 싶은 문자열 N이 주어진다.(0 < |N| ≤ 10)

단, N과 H는 공백 없는 문자열로 주어지며, 모두 알파벳 대문자로 이루어져 있다.

출력

H에서 N이 몇 번 등장하는지 출력한다.


저작자표시

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

BOJ 백준온라인져지 12845 모두의 마블 풀이  (0) 2018.04.25
BOJ 백준온라인져지 2559 수열 풀이  (0) 2018.04.25
BOJ 백준온라인져지 5671 호텔 방 번호 풀이  (0) 2018.04.23
BOJ 백준온라인져지 2592 대표값 풀이  (0) 2018.04.23
BOJ 백준온라인져지 8394 악수 풀이  (0) 2018.04.20

1. i -> j 로 도착하는것만 중요하다

2. 중간에 있던 내용들은 다 삭제해준다.

3. 감을 못잡겠어서 출제자의 정해를 보고 풀었다.

import java.io.*;
import java.util.*;
/**
* https://www.acmicpc.net/problem/15562
* BOJ 백준온라인져지 15562 네트워크 풀이
*/
public class Main {
private static boolean visited[];
private static int result = 0;
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 = Integer.parseInt(str1[1]);
int in[] = new int[N + 1];
int out[] = new int[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]);
out[A]++;
in[B]++;
}
result = 0;
for (int i = 1; i <= N; i++) {
result += Math.max(0, out[i] - in[i]);
}
bw.write(String.valueOf(result));
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

우리의 회사에는 N개의 네트워크 시스템 S1, S2, ..., SN와 이들을 연결하는 M개의 네트워크들 W1, W2, ..., WM이 있다. 네트워크 시스템들은 우선순위가 있어 모든 네트워크는 우선순위가 높은 곳에서 낮은 곳으로만 전달된다. 즉, SA에서 SB로 전달되는 네트워크가 있다면 A < B 이다.

최근 이 네트워크 시스템이 너무 난잡해져 이를 정리하기로 했다. 이를 설명하자면, 시스템 SA, SB, SC에 대해서 SA에서 SB로 전달되는 네트워크와 SB에서 SC로 전달되는 네트워크가 있다면 이 둘을 합쳐 SA에서 SC로 전달되는 네트워크로 간략화하는 것이다. 이 방식으로 간략화를 반복해서 최대한 네트워크의 수를 줄이고자 한다. 이 때, 남은 네트워크의 수를 구하여라.

입력

첫 번째 줄에 N와 M이 주어진다. (1 ≤ N, M ≤ 106)

M줄 동안 두 숫자 Ai, Bi가 주어진다. 이는 Wi가 SAi와 SBi를 연결함을 뜻한다. (i = 1, 2, ..., M, 1 ≤ Ai < Bi ≤ N)

출력

최대한 간략화했을때 남은 네트워크의 수를 출력한다.


저작자표시

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

BOJ 백준온라인져지 9506 약수들의 합 풀이  (0) 2018.03.13
BOJ 백준온라인져지 1094 막대기 풀이  (0) 2018.03.13
BOJ 백준온라인져지 15565 귀여운 라이언 풀이  (0) 2018.03.11
BOJ 백준온라인져지 2669 직사각형 네개의 합집합의 면적 구하기 풀이  (0) 2018.03.10
BOJ 백준온라인져지 2668 숫자고르기 풀이  (0) 2018.03.10
import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/contest/problem/271/1
* BOJ 백준온라인져지 271/1 A번 - 부당한 퍼즐 풀이
*/
class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
if (N == 1) {
System.out.println("good puzzle");
return;
}
int d1[][] = new int[N + 1][2];
int d2[][] = new int[N + 1][2];
String str1[] = br.readLine().split(" ");
String str2[] = br.readLine().split(" ");
int pre = Integer.parseInt(str1[0]);
d1[pre][0] = Integer.parseInt(str1[str1.length - 1]);
d1[pre][1] = Integer.parseInt(str1[1]);
int last = Integer.parseInt(str1[str1.length - 1]);
d1[last][0] = Integer.parseInt(str1[str1.length - 2]);
d1[last][1] = pre;
for (int i = 1; i < N - 1; i++) {
int cur = Integer.parseInt(str1[i]);
d1[cur][1] = Integer.parseInt(str1[i + 1]);
d1[cur][0] = pre;
pre = cur;
}
pre = Integer.parseInt(str2[0]);
d2[pre][0] = Integer.parseInt(str2[str2.length - 1]);
d2[pre][1] = Integer.parseInt(str2[1]);
last = Integer.parseInt(str2[str2.length - 1]);
d2[last][0] = Integer.parseInt(str2[str2.length - 2]);
d2[last][1] = pre;
for (int i = 1; i < N - 1; i++) {
int cur = Integer.parseInt(str2[i]);
d2[cur][1] = Integer.parseInt(str2[i + 1]);
d2[cur][0] = pre;
pre = cur;
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 2; j++) {
if (d1[i][j] != d2[i][j]) {
if (d1[i][0] == d2[i][1] && d1[i][1] == d2[i][0]) continue;
System.out.println("bad puzzle");
return;
}
}
}
System.out.println("good puzzle");
}
}
view raw BOJ_271_1.java hosted with ❤ by GitHub

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

BOJ 백준온라인져지 5430 AC 풀이  (0) 2018.02.27
BOJ 백준온라인져지 1021 회전하는 큐 풀이  (0) 2018.02.26
BOJ 백준온라인져지 10866 덱 풀이  (0) 2018.02.22
BOJ 백준온라인져지 1966 프린터 큐 풀이  (0) 2018.02.20
BOJ 백준온라인져지 10610 30 풀이  (0) 2018.02.17

+ Recent posts

티스토리툴바