Problem Solving (22) 썸네일형 리스트형 [ACMICPC] 1717 . 집합의 표현 1717번 집합의 표현 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 두 원소가 같은 집합인지 판단하는 알고리즘이 있다. 대놓고 Union Find를 쓰라는 문제였다. 2. Union Find 코드 1234567891011static int find(int a){ if(parent[a] [ACMICPC] 2469 . 사다리 타기 2469번 사다리 타기 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 사다리 문제는 가로 줄 하나에 상태 두개가 swap된다는 것을 알고 있으면 좋다. Wildcard가 되는 줄을 line이라고 하면, 0부터 line전 까지 map을 돌면서 status를 갱신한 것과 n-1부터 line전 까지 map을 돌면서 status를 갱신한 것 이 두가지가 같은 위치에서 상태가 다른지를 보면서 답을 구해나가면 된다. 2. status 구하는 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 String in = br.readLine(); for(int i=0;i [ACMICPC] 3005 . 크로스워드 퍼즐 쳐다보기 3005번 크로스워드 퍼즐 쳐다보기 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? R과 C가 20이고 BruteForce로 모든 행,열을 두 번씩 돌아도 O(R*C*2) 로 시간제한은 생각하지 않아도 된다. 모든 행을 왼쪽->오른쪽으로, 모든 열을 위->아래로 돌면서 길이가 2이상인 모든 문자를 탐색하면 된다. 2. 특정 행,열의 처음에서 시작하는 탐색 코드 12345678910111213141516171819202122232425static int[] dy={1,0},dx={0,1}; // ... static String getLongestWord(int y,int x,int dir){ String ret = "zzzzzzzzzzzzzzzzzzzzzzzzzzz"; StringBuilder s.. [ACMICPC] 9019 . DSLR 9019번 DSLR 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? String 연산이 반복되고 시간 제한이 6초인걸 보니 연산을 줄일 수 있는 부분은 모두 최소화해야겠다고 생각했다. 최소한의 명령어는 BFS로 생각할 수 있고 그 명령어 나열은 String을 붙여서 구현할 수 있다. 명령어의 나열에서 처음에 StringBuilder를 생각했는데 어차피 Queue에 들어가는 각 상태마다 새로운 객체가 필요해서 그냥 String으로 사용할 수 밖에 없었다. 실제 값 비교는 String이 아닌 int로 연산하여 시간을 줄이고자 했다. 2. DSLR 코드 1234567891011121314151617181920212223242526272829303132333435363738// Dint dval = (.. [ACMICPC] 14938 . 서강 그라운드 14938번 서강 그라운드 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 정점, 길의 개수가 적기 때문에 플로이드,다익스트라 모두 쓸 수 있다. 2. 전체 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374import java.io.*;import java.util.*; public class 서강그라운드 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer .. [ACMICPC] 10250 . ACM 호텔 10250번 ACM 호텔 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? Bruteforce 이중 포문으로 모든 층을 한번씩 방문하여 돌면서 cnt 수를 갱신해나가다가 N과 cnt가 같아지는 순간의 층의 방 번호를 출력하면 된다. 1234567891011121314151617 static void solveByBruteforce() throws IOException{ int cnt = 0; for(int j=1;j [ACMICPC] 13469 . 시간표 짜기 14569번 시간표 짜기 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? BruteForce 모든 과목의 수업 시간을 하나씩 체크하면서 그 시간이 비는지 체크한다. 이 경우 O(N*k*M) = O(500,000,000)으로 시간 제한을 넘긴다. 다른 방법이 필요하다. BitMask 결국 어떤 과목과 학생의 시간을 탐색하는 방법의 최적화가 필요하다. 시간이 1 50 사이로 주어지므로, 64Bit 자료형을 사용하여 1 50 사이의 주어지는 시간의 Bit를 켜두고 &연산자를 활용하면 50번의 비교를 1번의 비교로 줄일 수 있다. 2. BitMask 코드 1 2 3 4 5 6 7 8 9 N = Integer.parseInt(br.readLine()); long[] lectures = new long[N.. [ACMICPC] 18111 . 마인크래프트 18111번 마인크래프트 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 땅의 높이가 최대 256이므로 0부터 256까지 높이를 한 번씩 설정해보고 그 높이로 평탄화하는 방법을 생각할 수 있다. 맵의 크기는 최대 500이므로 250,000이다. 250,000*257 = 64,250,000이므로 1초 제한인 이 문제에서 모든 블럭을 한 번씩 돌면서 높이를 체크하는 방법을 쓰기는 불안하다. 모든 맵을 돌지 않아도 땅의 최대 높이가 256이므로 각 높이에 해당하는 블록의 개수를 미리 저장해둘 수 있다. 그리고 0~256까지 높이를 한 번씩 시도해보면서 현재 가지고있는 블럭들의 높이에 대해서 현재 설정한 높이를 만드는데 드는 비용을 계산할 수 있다. 2. 전체 코드 12345678910111213141.. 이전 1 2 3 다음