본문 바로가기

백 트래킹

 (10)
[백준 / BOJ] 12101 1, 2, 3 더하기 2 (cpp) 문제 출처 : https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 만들려는 숫자 n이 주어졌을때, n을 1,2,3을 이용해서 만들고 n을 만드는 경우의 수의 조합중 k번째를 찾아 출력하는 문제이다. 풀이 이런 유형의 DP를 풀어본적이 있어서 DP라고 착각했지만, n의 최댓값이 11로 작아서 완전탐색으로도 풀리는 문제다. 로직은 간단한데, 재귀를 이용해서 1,2,3으로 숫자 n을 만드는 모든 경우의 수를 저장해놓은다음 정렬 후 출력하면 된다. 주요 소스코드 void getComb(i..
[백준 / BOJ] 18430 무기 공학 (Java) 문제 출처 : https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net N*M그리드가 주어진다. 길동이는 N*M그리드의 각 칸을 적절히 잘라서 부메랑을 만들어야한다. 길동이가 만들수있는 부메랑들의 크기의 총합을 가장 크게하는 프로그램을 만드는 문제다. 풀이 N과 M이 5가 최대이므로 완전탐색으로 풀수있는 문제였다. 백 트래킹으로 구현한 전형적인 백트래킹 문제다. 구현중 주의할점은 아래와 같다. 현재 위치를 y,x라 했을때, 다음에 탐색..
[백준 / BOJ] 9944 N*M 보드 완주하기 문제 출처 : https://www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net N*M크기의 보드에 장애물(*) 빈칸(.)이 있다 보드의 빈칸위에 놓인 공은 다음 규칙에따라 움직인다. 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속해서 이동시킨다. 공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속해서 이동한다. 게임은 공이 더 이상 이동할 수 없을때 끝난다. 모든 빈칸을 방문하기위한 이동횟수의 최솟..
[백준 / BOJ] 1097 마법의 단어 문제 출처 : https://www.acmicpc.net/problem/1097 1097번: 마법의 단어 첫째 줄에 단어의 개수 N이 주어진다. N은 8보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 20이다. 단어는 알파벳 대문자로만 이루어져 있다. 마 www.acmicpc.net N개의 단어가 있다. N개의 단어를 적절히 조합하여 (이때, N개의 단어를 전부 사용해 조합해야한다) 문자열 T를 만든다. 문자열 T의 시작지점을 i만큼 오른쪽으로 이동시켰을때 문자열을 T(i)라 한다. (문자열 ABCD를 오른쪽으로 2만큼 움직인후 문자열은 CDAB가 된다.) 이때, 문자열 T와 바뀐문자열 T(i)가 정확히 일치하게되는 i가 k개 있으면, 이 문자열을 "마법의..
[백준 / BOJ] 9874 Wormholes (Java) 문제 출처 : https://www.acmicpc.net/problem/9874 9874번: Wormholes Farmer John's hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2
[백준 / BOJ] 1248 맞춰봐 문제 출처 : www.acmicpc.net/problem/1248 1248번: 맞춰봐 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 www.acmicpc.net 규현이는 -10 ~ 10 까지 총 21개의 숫자를 알고있으며, 이 수를 구간합으로 나타냈다. S[i][j] 는 i번째 숫자부터 j번째 숫자까지의 구간합이며 이 값이 양수면 +, 음수면 -, 0이면 0이 된다. S[i][j]의 각 원소들이 모두 주어졌을때 원래 수열이 무엇인지 찾는 문제였다. 풀이 완전탐색(백 트래킹)으로 풀리는 문제였다. 각 칸에 숫자를 넣어보고 숫자를 넣을수있다면, 재귀를 호출..
[백준 / BOJ] 1035 조각 움직이기 문제 출처 : www.acmicpc.net/problem/1035 1035번: 조각 움직이기 최대 5개의 조각이 있는 5*5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net 5*5크기의 보드에 최대 5개의 조각이있다. 이 조각을 적절히 움직여서 모든 조각이 연결되도록 할려고한다. 조각은 상하좌우 한칸으로 이동시킬수 있다고할때, 모든 조각을 연결하는 최소한의 이동 횟수를 구하는 문제다. 풀이 처음에는(1년전??) BFS로 풀려했는데, BFS는 항상 최단경로를 보장하므로 하나의 조각을 기준으로 잡고 나머지 조각을 해당 조각으로 이동하는 횟수를 BFS로 구해주는로직을짰..
[백준 / BOJ] 14502 연구소 문제 출처 : www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net N*M그리드가 주어지고, 그리드의 상태가 주어진다. 0 : 빈칸 1 : 벽 2 : 바이러스 바이러스는 매초 상하좌우 빈칸으로 확산될수있다. 바이러스가 모두 확산된후 남아있는 빈칸의 수를 안전영역이라 한다. N*M그리드에 벽 3개를 적절히 설치했을때, 안전영역의 최대 크기를 구하는 문제다. 풀이 N과 M의 범위가 크지않아, 완전탐색으로 풀리는문제다. 시간복잡도는 1. N*M그리드 에서 3개의 빈칸을 선택하는 경..

티스토리툴바