본문 바로가기

백준4

[BFS] 백준 16948 : 데스 나이트 16948번: 데스 나이트 (acmicpc.net) 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 1. 양방향 / 일방향으로 이동 가능한(연결된) input이 주어지거나, 각 점으로부터 이동 가능한 점에 대한 규칙이 주어진다. 2. 최단거리, 최단루트를 묻는다 => BFS BFS 문제들을 예전에 몇 개 풀었었지만, 한동안 다른 카테고리의 문제들 위주로 접하다가 오랜만에 BFS 문제를 보니 어떻게 BFS를 구현하는지 잘 기억이 안 났.. 2022. 8. 2.
[BruteForce] 백준 2309: 일곱 난쟁이 2309번: 일곱 난쟁이 (acmicpc.net) 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 간만에 브론즈 문제. 내가 브루트포스 문제가 많이 약한데 그래도 쉽게 풀 수 있던 문제였다. 9명 중 7명을 고르는 경우의 수는 사실 택도 없이 작기 때문에, 브루트포스를 써도 될지 고민할 필요는 없었다. 먼저, 난쟁이들의 키를 저장하기 위한 배열 dwarf, 해당 난쟁이가 체크되었는지 확인하는 배열 isChecked를 만들었다. static int[] dwarfs = new int[9]; static boolean[] .. 2022. 7. 28.
[구현] 백준 20061: 모노미노도미노 2 이번 문제도 엄청 길어서 캡처 대신 링크로 갈음한다. 20061번: 모노미노도미노 2 (acmicpc.net) 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 어제 새벽 서너시까지 잡고 풀었는데, 문제가 딱히 되짚을 게 없다... 그냥 빡구현이다. 채워넣고, 조건 맞으면 점수 올리고, 연하게 색칠된 특별 구역에 들어가면 그만큼 내려주고... 만 반복하면 된다. 어차피 빨강 배열은 볼 필요가 없다. 초록 배열, 파랑 배열만 가지고 작업하면 된다. 어떤 블록을 넣어줄지 지정해주는 t, 배열이 들어갈 인덱.. 2022. 7. 27.
[DP] BOJ_2133: 타일 채우기 도저히 규칙을 찾지 못해서 고생깨나 했던 문제이다. 결국 규칙을 못 찾아서 구글링을 통해 힌트를 얻고 나서야 비슷하게 도전해 볼 수 있었다. 사실 DP 관련한 문제들이 다 규칙을 찾기만 하면 무난하게 풀 수 있는데, 규칙을 못 찾아서 문제가 되는 것 같다. 규칙은 다음과 같다. 1. n이 홀수인 경우, 타일을 채우는 경우가 존재하지 않는다. 2. n이 짝수인 경우, '독특하게' 타일을 채우는 방법이 2가지씩 존재한다. 사실 여기까지는 나 스스로도 바로 찾아낼 수 있었지만, 이 이후로 이것을 규칙화하는 데 문제가 발생하였다. 그리고 그 문제를 해결해 주는 키워드는 '나누어서 생각하기' , 그리고 '함수처럼 생각하기' 였다. 우선, 3*n size의 벽을 채우는 경우의 수를 f(n)이라고 하자. 그렇다면 가.. 2022. 6. 29.

티스토리툴바