전체 글

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]``..

2193 - 이친수https://www.acmicpc.net/problem/2193문제이친수(pinary number): 0과 1로만 이뤄진 수1. 0으로 시작 X2. 1이 2번 연속으로 나타나지 X (11을 부분 문자열로 갖지 X)ex. 1, 10, 100, 101, 1000, 1001 등But, 0010101 or 101101은 X입력: N (1 출력: N자리 이친수의 개수풀이`dp[i]`: 길이 i일 때 이친수의 개수`dp[i] = dp[i - 1] + dp[i - 2]``dp[i - 1]`: 마지막 숫자가 0인 경우앞에 무슨 숫자든 상관 X => 길이 N - 1의 모든 이친수에 0만 붙이면 됨`dp[i - 2]`: 마지막 숫자가 1인 경우그 앞에 반드시 0이 와야 함 -> 마지막 두 자리가 01이..

1080 - 행렬https://www.acmicpc.net/problem/1080문제0과 1로만 이뤄진 행렬 A, B행렬을 변환하는 연산은 어떤 3x3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것 (0 -> 1, 1 -> 0)=> 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값?입력첫째 줄: 행렬의 크기 N, M (N, M (자연수) 둘째 줄부터 N개의 줄: 행렬 A그 다음줄부터 N개의 줄: 행렬 B출력: 정답만약 A를 B로 바꿀 수 X => -1 출력풀이3x3 범위 => `i 0 1: `1 - A[x][y]`int cnt = 0;for (int i = 0; i 코드import java.io.*;import java.util.*;// 행렬public class boj_1080 { s..

1783 - 병든 나이트https://www.acmicpc.net/problem/1783문제병든 나이트가 N x M 크기 체스판의 가장 왼쪽아래 칸에 위치4가지로만 움직일 수 있음1. 2칸 위로, 1칸 오른쪽2. 1칸 위로, 2칸 오른쪽3. 1칸 아래로, 2칸 오른쪽4. 2칸 아래로, 1칸 오른쪽병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 함이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 함/ 4번보다 적은 경우(방문한 칸 => 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수?입력: 체스판의 세로 길이 N, 가로 길이 M (N, M (자연수) 출력: 여행에서 방문할 수 있는 칸의 개수 중 최댓값풀이행 =..