Min:D's Devlog

문제 백준 삼성 SW 역량 테스트 기출 문제 - 14500 테트로미노 (Gold 5) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 문제 풀이 접근 방식 아래의 테트로미노 중 하나를 회전하거나 대칭하여 주어진 종이에 놓았을 때, 놓인 칸에 쓰인 수들의 합의 최댓값을 구하는 문제이다. 우선, 각 테트로미노들을 회전하거나 대칭한 모양대로 탐색을 수행해야하기 때문에, 총 19개의 테트로미노들을 다음과 같이 구현하였다. int dir[5][2] = { {-1,0},{0,1},{1,0},{0,-1},{-1,1} };..

문제 백준 삼성 SW 역량 테스트 기출 문제 - 14501 퇴사 (Silver 4) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이 접근 방식 상담을 적절히 했을 때, 얻을 수 있는 최대 수익을 구하는 문제이다. 이 문제는 DP 방식으로 문제를 해결하였다. 우선, DP 벡터를 만들어 DP[i]에 i - 1일 동안 했던 상담의 최대 수익을 저장해주었다. i번째 날의 상담을 기간 내에 할 수 있는 경우에는, DP[i + 소요 기간]에 기존의 값과 (DP[i] + 수익)의 값 중 더 큰 값을 저장해주었다. 또한, 매번 다음날의 값과 현재의 값을 비교하여 더 큰 값을 DP[i+1]에 저장하였다. 위의 과정을 주어진 일정만큼 반복하면 DP[N+1..

문제 백준 삼성 SW 역량 테스트 기출 문제 - 14502 연구소 (Gold 5) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 문제 풀이 접근 방식 이 문제는 벽 3개를 세운 뒤, 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 문제이다. 우선, 3중 for문으로 벽 3개를 세운 뒤, DFS 함수를 만들어 바이러스를 퍼뜨려주었다. (입력 받을 때, 바이러스의 위치를 저장하여 BFS 방식으로 바이러스를 퍼뜨려줘도 된다.) 그 후, map에 있는 0의 개수를 세어 안전 영역의 크기를 구해주었다. 이 값을 max값과 비교하..

문제 백준 삼성 SW 역량 테스트 기출 문제 - 14888 연산자 끼워넣기 (Silver 1) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 문제 풀이 접근 방식 숫자와 각 연산자의 개수가 주어질 때, 만들 수 있는 식의 결과의 최댓값과 최솟값을 구하는 문제이다. 이 문제는 어떤 연산자를 먼저 사용할 지 결정하여 최종적인 식의 결과를 구하는 문제이기 때문에, DFS 함수를 만들어 답을 구해주었다. DFS 함수는 연산자의 개수를 저장한 벡터와, 현재 ..

문제 백준 삼성 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 역량 테스트 기출 문제 - 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 함수에서..