TIL

[JAVA] 백준 1890번 : 점프

1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 문제 NXN 게임판에 수가 적혀져 있다. 게임의 목표 : 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것 각 칸에 적혀 있는 수 : 현재 칸에서 갈 수 있는 거리 -> 반드시 오른쪽이나 아래로 가야함. -> 한 번 점프를 할 때, 방향을 바꾸면 안됨. -> 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두가지 경우만 존재. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 ..

[JAVA] 백준 3036번 : 링

3036번: 링 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌� www.acmicpc.net 문제 - 여러개의 링이 있고 그 링들의 반지름이 주어졌을때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램 입력 - 첫째 줄에 링의 개수 N (3 ≤ N ≤ 100) - 다음 줄에는 링의 반지름 (반지름은 1과 1000를 포함하는 사이의 자연수) 출력 - 출력은 총 N-1줄을 해야 한다. - 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력 풀이 원의 둘레 공식..

[JAVA] 백준 2609번 : 최대공약수와 최소공배수

2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램 입력 첫째 줄에는 두 개의 자연수 (10,000이하) 출력 -첫째 줄에는 입력으로 주어진 두 수의 최대공약수를 출력 -둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력 풀이 최대공약수 문제를 풀기 위해선 유클리드 호제법 이라는 알고리즘을 이용하면 쉽다! 유클리드 호제법이란 2개의 자연수(또는 정식)의 최대공약수를 구하는 알고리즘의 하나로, 호제법이라는 말이 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 이론은 ..

[JAVA] 백준 14501번 : 퇴사

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 - N+1일째 되는 날 퇴사 - 남은 N일 동안 최대한 많은 상담을 함 - 각각의 상담은 상담을 완료하는데 걸리는 기간 : Ti - 상담을 했을 때 받을 수 있는 금액 : Pi 이때 얻을 수 있는 최대 수익을 구하는 프로그램 - N = 7인 경우에 다음과 같은 상담 일정표 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다. 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게..

[JAVA] 백준 1932번 : 정수 삼각형

1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. - 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램 - 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택가능 - 삼각형의 크기는 1 이상 500 이하이다. - 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9..

[JAVA] 백준 2293번 : 동전 1

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 - n가지 종류의 동전이 주어지고, 각각의 동전이 나타내는 가치는 다를 때, 그 가치의 합이 k원이 되도록 하는 그 경우의 수를 구하는 프로그램. - 각각의 동전은 몇 개라도 사용가능 - 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우로 침. 입력 - 첫째 줄에 n, k가 주어짐. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) - 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. (100,000보다 작거나 같은 자연수) 출력 첫째 줄에 경..

[JAVA] 백준 9461번 : 파도반 수열

9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그..

[JAVA] 백준 11726번 : 2Xn 타일링

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 - 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력. 풀이 처음부터 노가다로 구해보니까 점화식이 나왔다. DP[N] = DP[N-1]+DP[N-2] 임을 확인할 수 있다.. public class bj11726 { public static void main(String[] args) { //..