Min:D's Devlog

문제 백준 삼성 SW 역량 테스트 기출 문제 - 14889 스타트와 링크 (Silver 3) 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 풀이 접근 방식 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 구하는 문제이다. 이 문제는 사람들을 두 팀으로 나눠 능력치를 계산하는 간단한 조합 문제였다. 우선 사람들의 능력치를 입력 받은 후, 팀을 나누기 위해 next_permutation을 사용해주었다. 인덱스를 0과 1로 나눠 팀을 나눠주었고, 각 팀의 능력치를 계산하여 능력치의 차이를 구해주었다. 구한 능력치의 차이를 answ..

문제 백준 삼성 SW 역량 테스트 기출 문제 - 14891 톱니바퀴 (Silver 1) 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 � www.acmicpc.net 문제 풀이 접근 방식 주어진 규칙대로 톱니바퀴를 회전시킬 때, 최종 톱니바퀴의 상태를 구하는 문제이다. 한 톱니바퀴가 회전할 때 옆의 톱니바퀴와 맞닿은 톱니의 극이 다른 경우, 옆의 톱니바퀴는 반대방향으로 회전하게 된다. 이를 고려하여 톱니바퀴를 회전시켜주었다. 우선, 회전시킬 톱니바퀴의 주변으로 퍼져나가며 함께 회전시킬 바퀴들을 탐색을 해야하기 때문에, BFS 함수를..

문제 백준 삼성 SW 역량 테스트 기출 문제 - 15685 드래곤 커브 (Gold 4) 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커� www.acmicpc.net 문제 풀이 접근 방식 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 문제이다. 드래곤 커브는 이전 세대의 커브를 시계 방향으로 90도 회전시켜 끝 점에 붙인 형태로 만들어진다. 우선, 이렇게 만들어지는 드래곤 커브에 규칙성이 있는지를 확인해보았다. 방향이 0으로 시작하는 커브의 경우 0 - 01 - 0121 - 01212..

문제 백준 삼성 SW 역량 테스트 기출 문제 - 15684 사다리 조작 (Gold 5) 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 문제 풀이 접근 방식 사다리에 가로선을 추가하여 i번 세로선의 결과가 i번이 나오도록 조작할 때, 추가해야 하는 가로선 개수의 최솟값을 구하는 문제이다. 우선 H×N 크기의 map 벡터를 만들어 사다리의 가로선들을 저장해주었다. 가로선의 왼쪽 부분과 오른쪽 부분을 구분해주어야 하기 때문에, 왼쪽 부분은 1, 오른쪽 부분은 -1로 저장하였다. 그 후, DFS 방식으로 탐색하여 ..

문제 백준 삼성 SW 역량 테스트 기출 문제 - 15686 치킨 배달 (Gold 5) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 풀이 접근 방식 이 문제는 폐업시키지 않을 치킨집을 최대 M개 골랐을 때, 도시의 치킨 거리의 최솟값을 구하는 문제이다. 이 문제를 풀기 위해 필요한 정보는 집의 위치와 치킨집의 위치이다. 그래서 입력을 받을 때 map을 만들어 값을 저장하지 않고, 집의 위치와 치킨집의 위치만 저장해주었다. 그 후, next_permutation을 활용하여 치킨집을 M..

문제 백준 삼성 SW 역량 테스트 기출 문제 - 15683 감시 (Gold 5) 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감�� www.acmicpc.net 문제 풀이 접근 방식 이 문제는 CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 문제이다. CCTV는 아래와 같이 번호에 따라 감시하는 방향이 다르다. 어느 방향으로 CCTV를 설치했을 때 사각 지대가 최소가 되는 지 구하는 문제이기 때문에, DFS 함수를 만들어 모든 CCTV의 설치 방향(4방향)에 따른 사각 지대의 크기를 구해주었다. DFS 함수에서..

문제 백준 - 1261 알고스팟 (Gold 4) 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 풀이 접근 방식 이 문제는 0, 0에서 시작하여 N-1, M-1에 도달하기 위해 파괴한 벽의 개수의 최솟값을 구하는 문제이다. 그래서 BFS + DP의 방식으로 이 문제를 해결하였다. 우선, destroy라는 2차원 벡터의 모든 값들을 큰 수(987654321)로 설정해놓고,BFS 탐색을 수행하며 그 위치에 도달하기 위해 파괴한 벽의 개수의 최솟값을 destroy 벡터에 저장해주었다. 즉..