전체 글
[백준] 감시
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net DFS를 통한 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 다음 그림과 같이 4방향을 감시할 수 있는 cctv들이 놓여있는 방이 있습니다. 이 방에는 벽이 있고, 만약 벽이 있다면, cctv는 벽 뒷편은 보지 못합니다. 이 때, cctv의 사각지대를 최소화 시키는 것이 문제입니다. 실제로 문제가 조금 기니 한번 읽어보는 것을 권장합니다. DFS를 통해 각각의 cctv에 대해 가능..
[백준] 톱니바퀴
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 톱니 바퀴가 4개 있고, 각각 8개의 톱니를 가집니다. 이 때, 톱니들은 N, S극을 가집니다. 톱니는 바로 옆의 톱니와 붙어있는 곳의 극(N,S)가 다르면, 옆의 톱니와 반대방향, 같다면, 움직이지 않습니다. 이 때, 톱니바퀴를 회전시킨 방법이 주어지면, 최종적으로 톱니바퀴가 어떤 상태인지를 통해 구한 점수를 return 해야 합니다. 직접..
[백준] 경사로
https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 요약하면, NxN의 지도가 주어지고, 이 지도의 가로줄과 세로줄을 "길" 이라고 정의합니다. 이 때, 길들은 모두 높이가 같거나 경사로를 놓을 수 있는 경우에만 지나갈 수 있을 때, 경사로의 길이와, 지도가 주어질 때, 길중에서 지나갈 수 있는 길의 수를 구하는 것이 문제입니다. 문제의 조건이 조금 있으니 위의 링크에서 실제로 예시와 문제를 같이 읽어보는 것이 정확합니다. 구현 ..
[백준] 스타트와 링크
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 총 두가지 방법으로 해결할 수 있는 문제입니다. (직접 구현과, 아이디어) 우선 문제부터 간단하게 요약하면, 짝수명의 사람들을 두 팀으로 나누는데, 이때, 각각의 사람들이 서로 같은 팀에 있을 때의 캐미 점수가 표로 주어집니다.(팀캐미) 이 때 , 두 팀의 점수 캐미의 합 차이가 최소가 되도록 팀을 나눌 때, 점수 차의 최솟값을 구해야 하는 문제입니다. (실제로 문제를 한번 읽어보는 것을 추천합니다. ) 우선 시간이 ..
[백준] 로봇 청소기
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 구현 문제입니다. 문제부터 간단하게 요약하면, 로봇 청소기가 아래의 규칙대로 움직일 때, 1. 현재 위치를 청소한다. 2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 2-1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 2-2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 ..
[백준] 연구소
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 구현과, bfs 문제입니다. 우선 문제부터 간단하게 요약하면, 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 다음과 같이 연구소가 있는데, 0,1,2는 각각 빈 칸, 벽, 바이러스를 나타냅니다. 이곳의 빈 칸중 세군데에 벽을 추가로 설치하여 바이러스가 퍼지지 않은 방의 갯수를 최대로..
[백준] 퇴사
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dfs 또는 dp를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 각각의 상담은 소요시간과, 받을수 있는 금액으로 구성되어 있습니다. 매일 상담이 있을 때, 상담을 통해 최대 수익을 얻는 경우의 최대 수익의 값이 얼마인지를 구해야 하는 문제입니다. dfs와 dp를 사용한 풀이 두가지 모두 설명해 보겠습니다. 방법 1. DFS를 이용한 풀이 문제의 조건처럼 상담이 아래 그림과 같이 주어진다고 생각해 봅시다. 우리는 매 상담에 대해, 이 상담을 할지 말지를 결정합니다. 간단한 예시로 1일차를 생각해봅시다. 1일차에 상담을 진행하..