Coding Test

16930 - 달리기https://www.acmicpc.net/problem/16930문제다이어트를 위해 NxM 크기의 체육관을 달림체육관은 1x1 크기의 칸으로 나뉘어져 있고, 칸은 빈 칸 or 벽/ (x, y): x행 y열에 있는 칸 매 초마다 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향 하나 고르고, 그 방향으로 최소 1개, 최대 K개의 빈칸 이동=> 시작점 (x1, y1), 도착점(x2, y2) 주어졌을 때, 시작점에서 도착점으로 이동하는 최소 시간?입력첫째 줄: 체육관의 크기 N과 M, 1초에 이동할 수 있는 칸의 최대 개수 K둘째 줄 ~ N개의 줄: 체육관의 상태/ 빈 칸: '.', 벽: '#'마지막 줄: 네 정수 x1, y1, x2, y2 -> 두 칸은 서로 다른 칸이고 항상 빈 칸출력(x..

2110 - 공유기 설치https://www.acmicpc.net/problem/2110문제도현이의 집 N개가 수직선 위에 있고 각각의 집의 좌표는 $X_1$, ..., $X_N$집 여러 개가 같은 좌표를 가지는 일 X언제 어디서나 와이파이 즐기기 위해 공유기 C개 설치하려고 함/ 최대한 많은 곳에서 와이파이 사용하려고 함 -> 한 집에는 공유기 하나만 설치 O, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 함=> C개의 공유기 N개의 집에 적당히 설치 -> 가장 인접한 두 공유기 사이의 거리 최대입력첫째 줄: 집의 개수 N (2 둘째 줄부터 N개의 줄: 집의 좌표 $x_i$ (0 출력: 가장 인접한 두 공유기 사이의 최대 거리풀이이진 탐색(Binary Search)정렬된 데이터에서..

13011 - 사탕의 밀도https://www.acmicpc.net/problem/13011문제BOJ 알고리즘 캠프의 참가자 수는 N명이고, 0 ~ N - 1번까지 번호가 매겨져 있음i번 참가자는 총 C[i] 리터의 사탕이 들어가는 바구니를 가지고 있고, 받고 싶은 사탕의 무게는 W[i] 그램성원이는 모든 참가자들의 바구니를 가득 채워줄 것임(C[i] 리터만큼 모두 채울 것)But, 사탕을 한 종류만 만들 수 있음(밀도 일정) -> 되도록 많은 참가자를 만족시키는 밀도를 선택해야 함=> 최대한 많은 참가자 만족시키기 위해, 각 참가자의 W[i]와 실제로 받은 사탕의 무게 차이의 합 최소입력첫째 줄: 참가자 수 N (1 둘째 줄: C[i] / 셋째 줄: W[i] (1 출력: 각 참가자의 W[i]와 실제로 ..

11644 - 선분과 점https://www.acmicpc.net/problem/11664문제3차원 좌표 평면 위에 선분 하나와 점 하나선분의 양 끝점: A(Ax, Ay, Az)와 B(Bx, By, Bz)/ 점의 좌표: C(Cx, Cy, Cz)(x1, y1, z1)과 (x2, y2, z2) 사이의 거리 = $\sqrt{(x2-x1)^2+(y2-y1)^2+(z2-z1)^2}$=> 선분과 점 사이의 거리의 최솟값?입력선분과 점의 좌표 Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz (0 출력: 선분과 점 사이의 거리의 최솟값절대/상대 오차 $10^{-6}$까지 허용풀이Point 클래스 3차원 좌표: (x, y, z)두 점 사이의 거리: `distanceTo()`선분 AB 위에서 t비율 지점의 ..

1699 - 제곱수의 합https://www.acmicpc.net/problem/1699문제어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다ex. 11 = $3^2 + 1^2 + 1^2$ (3개 항) = $2^2 + 2^2 + 1^2 + 1 ^2 + 1^2$ (5개 항)수학자 숌크라테스는 "11은 3개의 항의 제곱수 합으로 표현할 수 있다"고 말한다또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 최소 개수는 3개이다=> 주어진 자연수 N을 제곱수들의 합으로 표현할 때 그 항의 최소개수?입력: 자연수 N (1 출력: 주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수풀이`dp[i]`: i를 제곱수의 합으로 표현하는 데 필요한 최소 항의 개수`dp[..

2225 - 합분해https://www.acmicpc.net/problem/2225문제0 ~ N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수덧셈의 순서가 바뀐 경우는 다른 경우 ex. 1 + 2 != 2 + 1/ 한 개의 수를 여러 번 사용할 수 있음입력: 정수 N (1 출력: 답을 1,000,000,000으로 나눈 나머지풀이`dp[i][j]`: 정수 j개를 더해서 합이 i가 되는 경우의 수 `dp[0][i] = 1`: i로 0을 만드는 방법 1가지 `dp[0][1] = 1`: 정수 1개로 0을 만드는 방법: 0 => 1가지int[][] dp = new int[N + 1][K + 1];for (int i = 1; i `dp[i][j] = dp[i][j - 1] + dp[i - 1][j]``..