분류 전체보기

9251 - LCShttps://www.acmicpc.net/problem/9251문제LCS(Longest Common Subsequence, 최장 공통 부분 수열): 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것 찾기ex. ACAYKP, CAPCAK의 LCS: ACAK입력: 첫째 줄과 둘째 줄에 알파벳 대문자로 이뤄진 두 문자열 주어짐 (최대 1000글자)출력: 주어진 두 문자열의 LCS 길이풀이`dp[i][j]`: str1의 i번째 문자까지, str2의 j번 문자까지 고려했을 때 LCS 길이`str1[i - 1] == str2[j - 1]` -> `dp[i][j] = dp[i - 1][j - 1] + 1`=> 두 문자 같으면 지금 문자를 LCS에 포함`str1[i - 1] !..

1149 - RGB 거리https://www.acmicpc.net/problem/1149문제RGB 거리에는 집이 N개 있음/ 거리는 선분으로 나타낼 수 있고 1 ~ N번 집 순서대로 있음집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 함/ 각각의 집을 rgb로 칠하는 비용 주어졌을 때 규칙 만족하면서 모든 집 칠하는 비용의 최솟값- 1번 집 색 != 2번 집 색- N번 집 색 != N-1번 집 색- i (2 입력첫째 줄: 집의 수 N (2 둘째 줄 ~ N개 줄: rgb로 칠하는 비용 (출력: 모든 집을 칠하는 비용의 최솟값풀이색 인덱스: 0 (빨강) / 1 (초록) / 2(파랑)`dp[i][j]`: i번째 집까지 칠했을 때, i번 째 집의 색이 j일 때의 최소 비용`dp[i][0] = min(dp[i ..

2166 - 다각형의 면적https://www.acmicpc.net/problem/2166문제2차원 평면상에 N(3 => 다각형의 면적입력첫째 줄: N다음 N개의 줄: 다각형을 이루는 순서대로의 x, y좌표 (x, y 출력: 면적/ 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 풀이신발끈 공식N개의 꼭짓점 (x1​,y1​),(x2​,y2​),...,(xN​, yN​)이 반시계/시계 순서로 주어졌을 때면적 = $|Σ(x_i * y_{i+1}) − Σ(y_i * x_{i+1})| / 2$/ 마지막은 다시 첫 점과 이어줘야 함$x_{N+1​} = x_1$$y_{N+1} = y_1$​long sum1 = 0;long sum2 = 0;for (int i = 0; i 코드import java.io.*;impo..

1106 - 호텔https://www.acmicpc.net/problem/1106문제홍보할 수 있는 도시가 주어지고 각 도시별로 홍보하는데 드는 비용/ 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보ex. 어떤 도시에서 9원 들여서 홍보 -> 3명 고객 늘어남 => 돈에 정수배만큼 투자할 수 있음9원 -> 3명, 18원 -> 6명, 27원 -> 9명 (O) / 3원 -> 1명, 12원 -> 4명 (X)=> 호텔 고객 적어도 C명 늘이기 위해 투자해야 하는 돈의 최솟값입력첫째 줄: C (둘째 줄 ~ N개 줄: 도시에서 홍보할 때 대는 비용, 그 비용으로 얻을 수 있는 고객 수 (출력: 문제의 정답풀이배낭 문제(Knapsack Problem)제한된 무게/비용 안에서 가치/이익을 최대화해서 조합 찾는 문제..

1707 - 이분 그래프https://www.acmicpc.net/problem/1707문제이분 그래프(Bipartite Graph): 그래프의 정점의 집합을 둘로 분할해 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할한 그래프입력첫째 줄: 테스트 케이스 개수 K각 테스트 케이스 첫째 줄: 그래프 정점의 개수 V, 간선의 개수 E (각 정점에는 1부터 V까지 차례로 번호)둘째 줄 ~ E개 줄: 인접한 두 정점의 번호 u, v (u != v, 간선의 대한 정보)출력: 이분 그래프 O -> YES / X -> NO 순서대로 출력풀이이분 그래프그래프의 모든 정점을 두 그룹(A, B)로 나눴을 때 인접한 두 정점이 같은 그룹 속하지 않게 나눌 수 있어야 함 = 인접한 정점은 항상 반대편 그룹이어야 함 시작..

14502 - 연구소https://www.acmicpc.net/problem/14502문제바이러스 확산을 막기 위해 연구소 벽을 세우려 함연구소 크기 NxM 직사각형, 직사각형은 1x1 정사각형으로 나눠져 있음/ 빈 칸, 벽으로 이뤄져 있으며 벽은 칸 하나를 가득 차지/ 일부 칸은 바이러스 존재, 상하좌우로 인접한 빈 칸 모두 퍼져나갈 수 있음/ 세울 수 있는 벽의 개수 3개고 꼭 세워야 함=> 연구소 지도가 주어졌을 때 얻을 수 있는 안전 영역의 크기의 최댓값입력첫째 줄: 지도의 세로 크기 N, 가로 크기 M (3 둘째 줄 ~ N개의 줄: 지도 모양 (0 빈 칸, 1 벽, 2 바이러스) (2 출력: 얻을 수 있는 안전 영역의 최대 크기풀이DFS(백트래킹)벽 세우기 벽 3개 세우면 바이러스 퍼트리기(`b..