반응형 Problem Solving155 백준 17143 : 낚시왕 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net [ 문제풀이 ] 이번에도 역시 주어진 조건대로 시뮬레이션하는 문제이다. 문제를 해결하는 다양한 방법이 존재하겠지만 나는 우선순위 큐를 활용하여 각 좌표의 상어들을 관리하는 식으로 해결하였다. 주의해야 할 점은 상어를 이동시킬 때 상어의 속도만큼 이동하는 방식으로 처리한다면 시간 초과가 발생할 것이다. 상어는 최대 1만 마리이며 상어의 속력은 최대 1000이기 때문에 단순히 이.. 2021. 8. 3. 백준 17144 : 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net [ 문제풀이 ] 이번에도 역시 주어진 조건대로 시뮬레이션하는 문제이다. 공기 청정기에 의해 미세먼지들이 한 칸씩 이동하는 것을 경우에 따라 나눠서 구현하는 것도 가능하지만 위, 아래 청정기의 방향을 따로 변수를 만들어 dfs를 돌리는 식으로 하면 훨씬 더 직관적이고 수월하게 구현할 수 있다. 또한, 모든 미세먼지가 확산되고 난 후 미세먼지 전체 값을 갱신해줘야 하기 때문에 2개의 2차원 배열을.. 2021. 8. 3. 백준 16235 : 나무 재테크 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net [ 문제풀이 ] 이번에도 역시 주어진 조건대로 시뮬레이션하는 문제이다. 특별한 알고리즘이 요구되는 문제는 아니지만 시간이 굉장히 타이트한 문제이기 때문에 자료구조 선택을 잘해야 할 것이다. 나는 처음에 나이가 어린 나무부터 양분을 먹는다는 조건 때문에 우선순위 큐를 사용하여 구현했지만 우선순위 큐는 원소 하나를 뽑아낼 때마다 O(log N)의 시간이 걸리기 때문에 적합한 자료구조.. 2021. 8. 3. 백준 16234 : 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net [ 문제풀이 ] 이번에도 역시 주어진 조건대로 시뮬레이션하는 문제이다. 골드 5의 난이도답게 정말 간단한 문제이다. dfs를 통해 경계선을 공유한 영역들을 나눠주기만 한다면 쉽게 해결할 수 있을 것이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.. 2021. 8. 3. 백준 7570 : 줄 세우기 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net [ 문제풀이 ] 여러 가지 테스트 케이스를 시도해보면 결국 주어진 수열에서 가장 긴 증가하는 연속 수열을 찾는 문제이다. dp 테이블을 다음과 같이 정의하자. dp[i] : i번째 숫자의 연속 수열 길이 증가하는 연속 수열을 찾는 것이기 때문에 dp[i]가 증가하기 위해선 (i - 1)번째 숫자가 i번째 숫자보다 먼저 등장해야 한다. 또한, dp 테이블의 정의에 따라 dp[i - 1]에는 (i - 1)번.. 2021. 8. 3. 백준 5373 : 큐빙 https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net [ 문제풀이 ] 지금까지 풀어본 삼성 SW 역량 테스트 기출문제들 중 가장 시간이 많이 걸린 문제이다. 단순한 시뮬레이션 문제이지만 완전 하드코딩 문제이기 때문에 디버깅하기도 어려웠고 그냥 빡셌던 문제인 것 같다. 1. 큐빙을 3차원이 아닌 아래와 같이 2차원 도면으로 표현한다면 구현하기가 조금 쉬울 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2.. 2021. 8. 2. 백준 15686 : 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net [ 문제풀이 ] 치킨집 중에 M 개를 선택해서 가능한 모든 경우의 수를 탐색하는 완전 탐색 문제이다. 조합 함수를 구현할 수만 있다면 쉽게 해결할 수 있을 것이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamRea.. 2021. 8. 2. 백준 15685 : 드래곤 커브 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net [ 문제풀이 ] 전형적인 시뮬레이션 문제로써 이전 드래곤 커브의 상태를 어떻게 관리하여 다음 드래곤 커브의 상태를 만들 것인지가 가장 중요하다. 다음 세대의 드래곤 커브는 끝 점을 기준으로 시계 방향으로 90도 회전한다고 하였다. 자세히 보면 끝점을 기준으로 지금까지 진행한 방향을 역순으로 90도 회전하면 다음 드래곤 커브를 만들어내는 것을 확인할 수 있다. 따라서 이.. 2021. 8. 2. 백준 15684 : 사다리 조작 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net [ 문제풀이 ] 전형적인 시뮬레이션 문제로써 백트래킹을 통해 0~3개까지의 사다리를 설치할 수 있는 모든 경우를 다 돌려보면 되는 문제이다. 사다리를 설치 후 가능한지 확인하기 위해 이동할 때 인덱스를 벗어나는 것을 방지하기 위해 넉넉하게 사다리 공간을 좌우로 +1칸씩 잡도록 하자. 사다리를 설치할 수 있는지를 판단할 때 현재 좌표만 판단하면 안 된다. 사다리가 연속되면 안 되기 때문에 현재.. 2021. 8. 2. 이전 1 ··· 10 11 12 13 14 15 16 ··· 18 다음 반응형
