본문 바로가기

백준4

백준 2110번 : 공유기 설치 문제를 보고 이해하는데 오래 걸리고, 힌트를 받았음에도 도통 모르겠어서 답을 찾아봤다. 많이 나온 답을 보고 해석한 내용이다. import java.io.*; import java.util.Arrays; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line = br.readLine().split(" "); int n = Integer.parseInt(line[0]); int c = Integer.parseInt(line[1]); int[] arr = new in.. 2021. 3. 26.
백준 2178번 : 미로탐색 미로 탐색은 대표 그래프 문제 중 하나이다. 최단 경로를 찾기 위해서 가장 작은 값으로 바꿔나가는 방식으로 생각했다. 예시를 봤을 때에는 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 은 1 0 9 10 11 12 2 0 8 0 12 0 3 0 7 0 13 0 4 5 6 0 14 15 이런 식으로 채워나가면 되겠다고 생각해서 dfs로 구현을 했다. 하지만, dfs 로 구현했을 때 시간 초과가 계속 떴다. dfs 는 최단경로를 찾기엔 적합한 방법이 아니기 때문이다. 일단 해를 찾으면 끝나는 dfs의 특성상 최단경로라는 최적의 해를 구할 수 없을지도 모른다. 밑의 글에 아주 잘 설명되어 있다. www.acmicpc.net/board/view/25832 라는 걸 극복하기.. 2021. 3. 23.
백준 2011번: 암호코드 경우의 수를 구하는 문제이다. 25114를 예시를 보면 1. 2,5,1,1,4 2. 2,5,1,14 3. 2,5,11,4 4. 25,1,14 5. 25,11,4 6. 25,1,1,4 위의 여섯 가지로 이루어져 있다. 백준 9095 번 문제와 규칙이 비슷한 양상으로 이루어졌다. dyii.tistory.com/7 백준 9095 번 : 1, 2, 3 더하기 dyii.tistory.com/6 백준 11727 번 : 2*n 타일링2 전에 풀었던 11726번 (2*n 타일링) 문제에 2 * 2 타일이 추가된 문제이다. dyii.tistory.com/5 백준 11726번 : 2*n 타일링 2 * 1 크기일 경우 1개 2 * 2 크기.. dyii.tistory.com 그래서 예시를 한 글자씩 따져보았다. 2 (1개) .. 2021. 3. 11.
백준 2579번 : 계단 오르기 규칙 세 가지를 지켜서 계단을 오르는 최댓값을 고르는 문제이다. 지켜야 할 규칙 1. 계단은 한 계단씩 또는 두 단계씩만 오를 수 있다. 2. 세 개의 계단을 연속적으로 밟을 수 없다. 3. 마지막 계단은 꼭 밟는다. 주의할 점. 1. 최댓값을 찾는데다가 밟을지 안 밟을지도 고려해야 하므로, 그 전의 기록을 계속 갖고 있어야 해서 기록을 하는 dp 배열이 필요하다. 2. 계단을 한 개 또는 두 개를 밟고 세 개를 연속적으로 밟을 수 없다는 것은, 지금의 계단에서 총 3개 아래의 값을 모두 확인해야 한다. 1. 첫 번째 계단을 밟는 경우. - 첫 번째 계단을 밟을 때 최댓값일 것이다. dp[0] = arr[0] 2. 두 번째 계단을 밟을 경우, - 두 번째 계단을 밟을 땐, 최댓값은 두 계단을 모두 밟는 .. 2021. 3. 5.

티스토리툴바