Dev.baelanche

BFS + 구현으로 풀었다. 인구이동을 시작할때 모든 노드에 대해 탐색을 시도해야 하므로 한번의 BFS만을 해서는 안된다. while(b) { cnt++; b = false; allbfs(); } public static void allbfs() { visited = new boolean[n][n]; for(int i=0; i

백트래킹으로 가능한 모든 팀을 구성한 뒤 최솟값을 구했다. 위의 예제로 설명하겠다. 1. 인덱스별로 DFS를 한다. 2. n/2 일때 방문한 노드2개 방문안한 노드2개 이므로 방문한 쪽/ 안한 쪽으로 팀을 나눈다. 3. 배열이나 리스트에 각 노드를 담아서 능력치 차이를 계산한다. 백트래킹을 제외하면 자기 스타일대로 구현을 하면 된다. public class Main { static int n; static int a[][]; static boolean visited[]; static int min = Integer.MAX_VALUE; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader..

문제 전문 이미지는 생략하도록 하겠다. N과 M 시리즈는 모~~두 백트래킹 문제로 시리즈별로 난이도 차이는 거의 없다. 백트래킹을 모른다면 간단히 공부하고 오거나 천재라면 필자의 빈약한... 소스를 보고 이해하면 되겠다. 15649번 : N과 M(1) ...더보기 중복없는 수열을 뽑아야 하므로 방문배열을 만들어 주어야 한다. 낮은 번호부터 순서대로 진행하며 배열체크만 해주면 된다. public class Main { static int n; static int m; static boolean visited[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStr..

단순 구현 문제다. 반복문 두번으로 가로줄, 세로줄을 긋고 두번째 줄을 예외처리 하는 방법으로 풀었다. 두번째 줄은 공백이 없으니 이 부분 주의해야한다..! public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int width = 1 + (n-1)*4; int height = 1; for(int i=0; i

입력된 수가 홀수 일때 정삼각형, 짝수 일때 역삼각형을 그리는 규칙을 가졌다. 삼각형은 외곽선만 존재하고 n 입력시 n-1, n-2, ... , (n>0일때까지) 를 재귀하며 내부에 삼각형을 그려야 한다. 문제 예제 출력 부분을 드래그 해보면 알 수 있을텐데 * 우측의 빈공간에는 공백이 없다. k*k 형식으로 우측을 공백으로 채우면 출력형식 오류를 반환하니 우측의 공백은 없애주어야 한다. 코드 클린 작업을 하지 않아서 지저분하지만 삼각형을 그리는 부분은 대충 확인 가능할 것이다. public class Main { static char a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc..

수의 범위가 너무 커서 문자열로 받아야 한다. 구현은 자기 입맛대로 하면 될듯 하다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); char a[] = sc.next().toCharArray(); char b[] = sc.next().toCharArray(); String sum = ""; int al = a.length - 1; int bl = b.length - 1; int upper = 0; while(al >= 0 || bl >= 0) { int s = 0; if(al >= 0 && bl >= 0) s = (a[al] - '0') + (b[bl] - '0') + uppe..

LIS 문제이다. 가장 큰 증가하는 부분 수열 문제와 답만 다를뿐 로직이 동일하다. 가장 긴 감소하는 부분 수열에 간단하게 풀이를 서술했다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; int dp[] = new int[n]; for(int i=0; i

백준 문제중 스티커를 먼저 푼 적이 있는데, 그 문제와 유사하다. 사자는 가로 혹은 세로로 연속된 우리에 놓을 수 없기 때문에 우리에 놓을 때 이전 우리의 상태를 파악해야 한다. 우리의 상태는 0(사자가 없음), 1(좌측에 사자를 둠), 2(우측에 사자를 둠) 으로 구분했다. 0 일때 1, 2 에 1 일때 0, 2 에 2 일때 0, 1 에 사자를 배치할 수 있다. 탑다운 방식으로 짰다. public static int lion(int n, int status) { if(n == N) return 1; if(dp[n][status] != -1) return dp[n][status]; int ret = lion(n+1, 0) % 9901; if(status != 1) ret += lion(n+1, 1) % ..