Dev.baelanche

BFS 로 인접노드탐색을 하면 된다. DFS 로도 구현을 할 수는 있는데 노드 레벨 순서대로 타는 것이 아니기 때문에 시간이 너무 오래걸리게 된다. public class Main { static int n; static int m; static int a[][] = new int[100][100]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); for(int i=0; i

BFS 로 노드 a 에서 b 까지의 레벨을 구하는 문제이다. 너비 탐색 기법을 쓸 줄만 안다면 충분히 풀 수 있다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[][] = new int[101][101]; boolean visited[] = new boolean[101]; Queue q = new LinkedList(); int a = sc.nextInt(); int b = sc.nextInt(); int m = sc.nextInt(); while(m-->0) { int x = sc.nextInt(); int y = sc...

예제로 풀이해보겠다. a[0] a[1] a[2] a[3] a[4] a[5] 점수 10 20 15 25 10 20 점수 배열이다. a[0] a[1] a[2] a[3] a[4] a[5] 첫번째 경우 10 20 15 25 10 20 두번째 경우 10 20 15 25 10 20 마지막 계단은 반드시 밟아야 하므로 뒤에서 되돌아오는 식으로 점화식을 구현해야 한다. dp[5] = dp[2] + a[4] + a[5]; dp[5] = dp[3] + a[5]; 중 큰 값을 선택한다. 두번째 경우에서 a[1] 을 썼는지 a[2] 를 썼는지 확인할 수 없으므로 dp[3]만 사용한다. 식으로 나타내면 dp[i] = max(dp[i-3] + a[i-1] + a[i], dp[i-2] + a[i]); 가 되겠다. 이런식으로 구현하..

간단한 dp 문제이다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 아래 인덱스는 위에 인접해 있는 인덱스 중 큰것을 골라 더해간다. 7 3+7 8+7 8+3+7 1+8+7 0+8+7 2+8+3+7 7+8+3+7 4+1+8+7 4+1+8+7 4+2+8+3+7 5+7+8+3+7 2+7+8+3+7 6+4+1+8+7 5+4+1+8+7 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]; 점화식은 위와 같다. dp[i][0] 일때는 -1의 인덱스로 접근할 수 있으므로 이것만 유의하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); ..

예제의 값으로 풀이 방법을 서술해보겠다. R G B dp[0][i] = a[0][i] 26 40 83 dp 배열의 첫번째 인덱스에는 입력받은 값을 받는다. R G B dp[0][i] 26 40 83 dp[1][i] 49 + 40 60 + 26 57 + 26 색상은 연속으로 칠할 수 없으므로 다른 색상 중 최소값을 받아 더한다. R G B dp[0][i] 26 40 83 dp[1][i] 49 + 40 60 + 26 57 + 26 dp[2][i] 13 + 60 + 26 89 + 57 + 26 99 + 60 + 26 마찬가지로 채워준다. dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + a[i][0]; dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + a[i][1..

경우를 나열해보면 평론가수 - (소시지 수와 평론가수의 최대공약수) 를 유추할 수 있다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); System.out.println(m - gcd(n, m)); sc.close(); } public static int gcd(int x, int y) { while(y != 0) { int tmp = y; y = x%y; x = tmp; } return x; } }

입력한 네 수 중 두개씩을 이어붙여 하나의 수로 만든다. 수가 자료형의 범위를 넘어가게 되므로 수를 문자열로 취급하여 풀어야 한다. 정말 지저분하지만 내가 푼 방법을 서술해보겠다. 1. 수를 문자형으로 입력받아 이어붙인다. 2. 만들어진 두 수의 길이를 비교해 짧은쪽의 앞을 0으로 채운다. 3. 맨 끝 인덱스부터 더하여 10 이상일 경우 자리올림을 한다. 3 - 1. 자리올림할때 맨 첫 자리일 경우엔 앞에 1을 채운다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String a = sc.next(); String b = sc.next(); String c = sc.next(..

주어진 정수의 자릿수가 증가할때마다 연산의 횟수도 증가한다. 1. n 이 10보다 클때 반복 연산한다. 2. k는 0부터 연산할때마다 1씩 증가하는 변수로 10^k로 n을 나눠 반올림 후 다시 10^k 를 곱해준다. 3. 출력 예제는 자연수이므로 자료형에 신경쓴다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); double n = sc.nextInt(); int k = 1; for(int i=10; true; i*=10) { if(n > i) { int pow = (int)Math.pow(10, k); n /= pow; n = Math.round(n); n *= pow; } e..