Dev.baelanche

입력된 수가 홀수 일때 정삼각형, 짝수 일때 역삼각형을 그리는 규칙을 가졌다. 삼각형은 외곽선만 존재하고 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) % ..

피보나치 수열과 비슷한 규칙을 가진 수열이다. 수열을 잘 살펴보면 dp[i] = dp[i-3] + dp[i-2] 와 같은 점화식을 얻을 수 있다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long dp[] = new long[101]; dp[0] = 0; dp[1] = dp[2] = 1; for(int i=3; i0) { int n = sc.nextInt(); System.out.println(dp[n]); } } }

유니온파인드 문제이다. 정답률이 높아서 쉬운줄 알았는데 꽤나 애먹었다. 아래와 같은 방법으로 풀었다. 1. 친구관계를 기록할 배열, 친구비용 배열, 친구번호와 비용을 모두 가진 클래스 배열을 만든다. 2. 친구관계가 주어지면 union 연산을 한다. 3. 클래스 배열의 루트 인덱스에 친구 비용의 최솟값을 저장한다. 4. k가 최솟값의 총합보다 같거나 크면 비용을 출력한다. public class Main { static int a[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; ..

유니온파인드 문제이다. 두 도시의 연결정보가 주어지면 union 연산을 한다. 여행계획이 주어졌을때 매 도시마다 find 연산을 하여 루트가 모두 같으면 YES 하나라도 다르면 NO를 출력한다. public class Main { static int a[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); a = new int[n]; Ar..

처음 풀어보는 유니온파인드 문제이다. 후에 되새기는 용으로 간단히 서술해보겠다. 유니온파인드(Union-Find)는 자료구조의 이름으로 disjoint-set(서로소 집합)이라고도 부른다. 1개 혹은 그 이상의 집합들은 서로 교집합이 없고 그 집합들의 합집합은 전체집합과 같다. 이 자료구조는 Union 연산(합연산)과 Find 연산(루트 검색)만이 있다. 문제 풀이 및 유니온파인드 구현을 같이 했다. public class Main { int tree[]; int size; Main(int size) { tree = new int[size+1]; this.size = size; Arrays.fill(tree, -1); } void set(int root, int child) { tree[child] = ..