Lee 코딩 Lee 코딩

연결 요소의 개수 시간 제한메모리 제한제출정답맞힌 사람정답 비율 3 초 512 MB 53979 25421 16603 44.000% 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 예제 입력 1 복사 6 5 1 2 2 5 5 1 3 4 4 6 예제 출력 1 복사 2 예제 입력 2 복사 6 8 1 2 2 5 5 1 3 4 4 6..

병든 나이트 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 8875 3826 3257 42.997% 문제 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다. 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서..

합분해 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 128 MB 25474 10987 7927 41.579% 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력 1 복사 20 2 예제 출력 1 복사 21 이 문제는 규칙 찾는데는 어렵지 않았지만 for문을 작성하는데 많이 헷갈렸다.. 풀이 : 일단 맨 앞에 숫자를 하나 고정시킨다고 생각하면 쉽다..

RGB거리 성공 시간 제한메모리 제한제출정답맞은 사람정답 비율 0.5 초 (추가 시간 없음) 128 MB 61297 29580 22050 48.293% 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진..

2×n 타일링 성공 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 256 MB 83129 30992 22585 35.015% 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 2 예제 출력 1 2 예제 입력 2 9 예제 출력 2 55 풀이 : 세로의 길이가 항상 2이므로 가로만 고려해도 된다. 따라서 가로를 1과 2만을 이용하여 어떻게 자를지 생각하여 풀면 된다. 즉, 이 문제는 n을 1과 2의 합으로 나..

문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 ..

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Test { static int n; static int m; static int[][] adjacent; static boolean[] visited; public static void main(String args[]) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer ..

풀이 방법 1. 일단 map[][]을 만들고 주어진 직사각형 좌표를 이용해 색칠된 직사각형 부분을 map[][] = 1로 만들어준다. 2. bfs를 이용하여 상하좌우 칸을 탐색하여 칠해지지 않은 부분이 있다면 count를 올려가며 영역의 넓이를 구한다. 3. bfs를 부를 때마다 areaCount를 1씩 증가시켜 분리되는 영역의 개수를 구한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static int[][] map; static boolean[][] visited; static int[] dx = {-1,1,0,0}; static int[] dy = {0,..