파게로그

문제 링크: 17825번 주사위 윷놀이 https://www.acmicpc.net/problem/17825 채점 현황을 보니 최적화된 코드에 비해 시간은 2배, 메모리는 5배 정도 더 잡아먹는 것 같다. 많은 개선이 필요해 보인다. move(): 하나의 horse 배열이 완성되었을 때, 점수를 구한다. board: board[i][j] = k이면 '출발지에서 도착지로 가는 4개의 경로 중 i번째 경로'의 'j 위치'에 '쓰인 숫자'는 k이다. horse: horse[i] = k이면 'i번째 주사위'에는 '말 k'를 움직인다. pos[i] = k이면 '말 i'의 위치는 k이다. score[i] = k이면 '말 i'의 점수는 k이다. path[i] = k이면 '말 i'는 '출발지에서 도착지로 가는 4개의 경..

문제 링크: 16235번 나무 재테크 https://www.acmicpc.net/problem/16235 전형적인 시뮬레이션 문제로서, 주어진 조건을 얼마나 꼼꼼하게 구현해내느냐가 중요하다. 웬일로 다른 풀이에 비해 메모리를 적게 사용하는 양질의 풀이를 뽑아냈는데, 아마 클래스를 정의하지 않고 ArrayList의 2차원 배열로서만 나무를 표현했던 것이 주요한 것 같다(컴파일러가 경고를 주는데, 검색해보아도 이를 해결할 수 있는 방법이 없다고 하는 것 같다...). import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.uti..

문제 링크: 19236번 청소년 상어 https://www.acmicpc.net/problem/19236 어쩌면 쉬운 문제인데, 나는 구현에서 상당한 어려움을 느꼈다. 다음 두 항목을 참고하면 빨리 풀릴 듯하다... 1. 상태공간트리를 DFS 방식으로 탐색할 경우, 함수 진입 후에 조건을 확인한다. 2. 백트래킹에서 원래 상태로 되돌리는 것이 어려울 경우, 이전의 상태를 아예 저장해서 복원시킬 수도 있다. 3. map에는 물고기의 번호만, arr에는 물고기 번호에 해당하는 인덱스에 물고기 객체를 저장한다. 1, 2번은 일반적인 구현 과정에서의 문제이다. 특히 1번의 경우, 별 생각없이 함수 진입 이전에 조건을 확인하니 return 값을 결정하는 데 있어서 굉장한 어려움을 겪었다. 3번은 자료구조를 어떻게..

문제 링크: 15686번 치킨 배달 https://www.acmicpc.net/problem/15686 치킨 집 중 m개를 뽑고, 각 집에서 가장 가까운 치킨집까지의 거리를 구한 후 이를 더해서 치킨 거리를 구한다. 이 치킨 거리가 최소일 때가 정답이다. 2차원 배열을 계속해서 이용하기보다는 집과 치킨집들의 좌표를 따로 저장해두고 이 두 배열만을 이용하는 것이 빠를 듯하다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; class P..

문제 링크: 20057번 마법사 상어와 토네이도 https://www.acmicpc.net/problem/20057 문제에서 나오는 대로 구현하면 되지만, 까다로운 부분이 있었다. 첫째로, 모래가 이동하는 목적지의 좌표를 토네이도의 방향에 따라 이동해주는 것이 까다로웠다. 직접 4개의 배열을 작성했는데, 이것보다 간결한 방법이 있는지 알아보아야겠다. 둘째로, α로 이동하는 모래의 양이 단순하게 55%가 아니라는 것이다. 셋째로, 토네이도의 이동 길이이다. 이동 거리를 0부터 시작해서 서쪽으로 이동할 때 또는 동쪽으로 이동할 때마다 이동 거리가 1씩 증가하도록 하였다. 넷째로, 토네이도의 이동 방향이다. dirCnt라는 변수를 통해 모듈러 연산을 활용했다. import java.io.BufferedRead..

문제 링크: 14890번 경사로 https://www.acmicpc.net/problem/14890 꼼꼼함이 요구되는 문제였다. 물론 처음부터 모든 경우의 수를 고려하는 것도 중요하겠지만, 현실적으로 스스로를 완전히 신뢰할 수는 없기에 많은 엣지 케이스를 테스트해보는 것도 좋은 방법일 것이다. 일단 가로든 세로든 각 길에 대해서 한 방향으로만 경사로를 놓을 수 있는지 체크하면 된다. 즉 예를 들어서 가로 길의 경우, 왼쪽에서 오른쪽으로 이동하면서 경사로를 놓을 수 있다면 오른쪽에서 왼쪽은 체크할 필요가 없다. 이 문제의 경우에는 다음과 같은 경우를 체크하는 것이 까다로웠다. 이를 위해서 내리막이 있을 때 먼저 내리막 이후의 평지에 대해서 시작 인덱스와 끝 인덱스를 구하고, 끝 인덱스 이후의 땅이 1만큼 ..

문제 링크: 7562번 나이트의 이동 https://www.acmicpc.net/problem/문제번호 평범한 BFS 구현을 통해 최단거리를 구할 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int[] drow = {-1, -2, -2, -1, 1, 2, 2, 1}; static int[] dcol = {-2, -1, 1, 2, ..

문제 링크: 4963번 제목 https://www.acmicpc.net/problem/4963 map을 순회하면서 육지인 지역(map[i][j]==1)이고 방문하지 않은 지역(!visit[i][j])인 경우에 DFS를 수행한다. 한 번 시행되고 나면 해당 육지와 연결된 지역은 모두 visit[i][j]는 true이므로 재방문되지 않고, 이러한 조건을 이용해서 섬의 개수를 센다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static int[] drow = {-1, -1, -1, 0, 1, 1, 1, 0}..