BOJ 12025 목표 : 영훈이는 장난꾸러기라서 희현이의 비밀번호 중 1은 6으로, 6은 1로 바꾸거나 2는 7으로 7은 2로 바꿔버렸다. 이를 해결하기 위해 희현이는 비밀번호 수열의 숫자 중 1과 6을 모두 1로, 2와 7을 모두 2으로 바꾼 숫자와 1과 6을 모두 6으로 2과 7을 모두 7로 바꾼 숫자 사이에 가능한 경우를 모두 사전순으로 나열한 다음 그 중 k번째 수열인 비밀번호를 찾기로 했다. 멘붕에 빠진 희현이의 비밀번호를 찾아주자. 조건 : K <= 2^63-1 0 <= 비밀번호의 자리수 <= 60 해결방안 k번째 비밀번호를 찾기위해서 가능한 비밀번호의 수열의 경우의 수는 1,2,6,7의 개수를 N개라고 할 때 2^N개이다. 이는 K를 2진수로 표현해 쉽게 해결할 수 있다. 예를 들어 K = 4이면 경우의 수는 0000~1111 까지 이고 0부터 시작하므로 0011번이 4번째 비

BOJ 14503 목표 : 로봇 청소기를 이동시킬 때 청소할 수 있는 영역의 수를 구하자. 조건 : 1 <= N,M<= 50, 현재 위치를 청소하고 왼쪽 방향으로 돌면서 청소할 영역을 탐색하고 해당 영역이 없으면 후진한다. 이때 후진할 영역이 벽이면 청소를 종료한다. 해결방안 벽과 청소한 영역을 잘 구분하자. 후진할 때는 방향은 바뀌지 않고 청소한 영역이라도 이동할 수 있다.

BOJ 14719 목표 : 2차원 세계에 블록이 있다. 비가 오면 블록 사이에 고인 빗물을 구하자. 조건 : 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 해결방안 이 문제는 두 가지 방법으로 해결할 수 있다. 반복문을 활용한 방법과 포인터를 활용한 방법이 있다. 우선 반복문을 활용한 방법은 빗물은 블록이 없는 빈 공간에만 존재할 수 있다. 각 높이의 양쪽 끝에서 블록을 만날 때까지 빈 공간을 체크하고 해당 공간을 제외한 영역의 넓이를 출력한다. ![](https://velog.velcdn.com/images/tmdtjq32/post/05c476c9-62f4-4

BOJ 14891 목표 : 톱니바퀴를 K번 회전시킨 후 점수를 구하자. 조건 : 1 <= K <= 100, 톱니바퀴는 8개의 톱니로 구성되어있다. 해결방안 전형적인 구현문제이다. 회전하는 톱니바퀴에 인접한 톱니바퀴의 좌우가 맞물릴 때 서로 다른 극이라면 해당 톱니바퀴도 반대방향으로 회전한다.

BOJ 15681 목표 : 트리를 입력받아 T번동안 정점 M를 루트로 하는 서브트리에 속한 정점의 수를 출력한다. 조건 : 1 <= 정점의 수(N) <= 100000, 간선의 수 = N-1, 1 <= T <= 100000 해결방안 매번 쿼리때 마다 트리를 순회할 경우 (10^5)^2 = 10^10, 최대 100억번을 반복해야한다. 한 번 트리를 순회하고 그때의 서브트리에 속한 정점의 수를 기록하자.

BOJ 15686 목표 : N*N형태의 지도에서 치킨집의 위치를 (cx,cy) 집의 위치를 (x,y)라고 했을 때 치킨집 중에서 |cx-x| + |cy-y| 거리가 최소인 값을 치킨 거리라고 한다. 각각의 집에서 치킨 거리의 합을 도시의 치킨 거리라고 한다. 최대 M개의 치킨 집만 남았을 때 도시의 치킨 거리의 최솟값을 구하자. 조건 : 1 <= N <= 50, 1 <= M <= 13, 1 <= 집의 개수 <= 2*N 해결방안 각각의 집에서 치킨집까지의 거리들을 구한 뒤 M개의 치킨 집을 골라 도시의 치킨 거리의 최솟값을 구한다. M개의 치킨 집을 고른다면 M-1, M-2개의 치킨집을 골랐을 때의 치킨 거리를 이미 포함하므로 재귀 함수를 활용해 M개의 치킨집을 골랐을 때 도시의 치킨 거리를 비교해 답을 구한다. ![](https://velog.velcdn.com/images/tmdtjq3

BOJ 16234 목표 : 조건에 맞게 인구이동이 몇 번 일어나는지 출력한다. 각 칸에서 상하좌우로 인접한 칸의 크기가 L이상 R이하라면 연합이 되고 인구 이동을 한다. 이때 각 나라의 인구 수는 (연합 국가들의 인구 수 총합 / 연합 국가 수)가 된다. 조건 : 1 <= N <= 50 해결방안 이 문제는 2단계로 구성할 수 있다. 연합을 구성하고 인구이동이 일어난 후 인구 수를 구한다. 각 연합들을 인구 이동 후 인구 수로 초기화한다. 만약 연합의 개수가 N*N개라면 모두 인구 이동을 하지 않으므로 마지막 인구 이동이 된다.

BOJ 17070 목표 : 파이프를 배치해 N*N칸으로 이동하자. 파이프는 가로, 세로, 대각선 3종류가 있다. 조건 : 3 <= N <= 16 해결방안 BFS를 통해 문제를 해결했다. 가로 파이프에서는 가로, 대각선, 세로 파이프에서는 세로, 대각선, 대각선 파이프에서는 모든 파이프를 설치할 수 있다. 추가로 설치할 곳에 벽이 있거나 배열을 나가지 않는지 체크하자.

BOJ 17396 목표 : 유섭이가 0번 노드에서 N-1까지 최단거리로 갈 수 있는 비용을 구하자. 유섭이는 백도어를 하러가는 것이기 때문에 와드가 있는 지역은 갈 수 없다. 유섭이가 갈 수 없다면 -1을 출력한다. 조건 : 1 <= N <= 100000, 1 <= M <= 300000, 1 <= cost <= 100000 해결방안 유섭이는 넥서스를 제외한 와드가 없는 지역으로 이동할 수 있다. 음수인 간선이 없어 음수 사이클이 없는 그래프이므로 다익스트라를 통해 해결했다. 간선의 비용(cost)이 100000이고 간선의 개수(M)가 300000이므로 300억의 비용이 나올 수 있다. 출발지부터 i번째 노드에 오는데 사용한 비용의 최소값을 저장할 dist배열을 int형 대신 long long형으로 사용하자. 우선 간선을 입력받을 때 간선이 이동하는 거리에 와드가 설치되어 있다면 그래프에 추

BOJ 17845 목표 : N개의 시간안에 T소요시간을 가지는 M개의 과목들을 수강해 얻을 수 있는 최대 중요도(I)를 구하기 조건 : 1 <= N <= 10000, 1 <= M <= 1000, 1 ≤ I ≤ 100000, 1 ≤ T ≤ 10000 해결방안 과목을 쪼개서 들을 수 없기에 0-1 배낭문제로 DP를 통해 해결할 수 있다. j의 소요시간을 가지며 i번째 과목을 선택했을 때 j시간에 얻을 수 있는 중요도의 최대값을 DPi으로 설정해 문제를 해결했다. 현재 들을 과목의 소요시간 : time, 현재 들을 과목의 중요도 : val time보다 j가 작은 경우 : dpi+1 = dpi j시간을 소모해 i+1번째 과목까지 들었을 때의 최댓값을 j시간을 소모해 i번째 과목까지 들었을 때의 최댓값으로 초기화한다. (어차피 지금 과목을 듣기에는 시간이 부족하기 때문에)