Dev.baelanche

피보나치 수열과 비슷한 규칙을 가진 수열이다. 수열을 잘 살펴보면 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] = ..

처음엔 문제 해석이 잘 안됐는데, 구간합을 합 대신 XOR로 구현하고 출력시에도 XOR하여 나타내면 된다. public class Main { 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()); int q = Integer.parseInt(st.nextToken()); int pxor[] = new int[n+1]; st = new Strin..

2차원 배열 구간합을 구현하면 된다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int r = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); int psum[][] = new int[r+1][c+1]; for(..

1차원 구간합 배열을 만들어 완전탐색으로 매 구간합의 최대값을 구한다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); while(t-->0) { int n = Integer.parseInt(br.readLine()); int psum[] = new int[n+1]; StringTokenizer st = new StringTokenizer(br.readLine()); for(int i=0; i

번역 역시나 발번역이다. 구간합을 저장할 배열을 만들어 품종별로 소의 개수를 따로 세어주면 된다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); int a[][] = new int[n][3]; int psum[][] = new int[..