전체 글
-
백준 16974번 레벨 햄버거PS 2020. 3. 19. 11:53
https://www.acmicpc.net/problem/16974 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1) 예를 들어, 레벨-1 버거는 'BPPPB', 레벨-2 버거는 'BBPPPBPBPPPBB'와 같이 생겼다. (B는 햄버거번, P는 패티) 상도가 상근날드에 방문해서 레벨-N 버거를 시켰 www.acmicpc.net 모든 햄버거에 대해 문자열의 형태로 저장한다면 메모리 초과가 나옵니다. 문제에서 주어진 마지막 테케를 보면 알 수 있죠. n번째 ..
-
백준 16948번 데스 나이트PS 2020. 3. 19. 11:43
https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부 www.acmicpc.net bfs 문제입니다. 이 문제는 이동방향이 상, 하, 좌, 우가 아닙니다. 문제에서 주어진대로 이동방향을 정의하면 됩니다. #inc..
-
백준 16928번 뱀과 사다리 게임PS 2020. 3. 19. 11:41
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다. 1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸 www.acmicpc.net bfs 문제입니다. 해당 지점이 뱀인지 사다리인지는 중요하지 않습니다. 다만 그 지점이 다른 좌표로 이동한다는 사실입니다. ..
-
백준 16968번 차량 번호판1PS 2020. 3. 19. 11:37
https://www.acmicpc.net/problem/16968 16968번: 차량 번호판 1 00부터 99까지 총 100가지 중에서 00, 11, 22, 33, 44, 55, 66, 77, 88, 99가 불가능하다. www.acmicpc.net 단순 구현 문제입니다. d가 연속해서 올 때, c가 연속해서 올 때를 구분하여 값을 계산했습니다. #include #include #include using namespace std; string s; int main() { cin >> s; int res = 0; for (int i = 0; i < s.length(); i++) { if (i == 0) { if (s[i] == 'd') { res += 10; } else { res += 26; } cont..
-
백준 17085번 십자가 2개 놓기PS 2020. 3. 18. 10:54
https://www.acmicpc.net/problem/17085 17085번: 십자가 2개 놓기 첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 완전 탐색문제 입니다. 7 7 ...#... ...#... ...#... ####### ...#### ...#.#. ...#... 이 테스트 케이스의 경우, 5*5로 답이 25입니다. 두 점이 선택되었을 때, 십자가 길이를 하나 하나 바꿔가면서 최대값을 찾아야 합니다. 구현이 조금 까다로운 문제입니다. #include #include using namespace std; int n, m, ..
-
백준 16943번 숫자 재배치PS 2020. 3. 17. 19:45
https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다. www.acmicpc.net 순열로 가능한 숫자배치를 만들어 본 후, 최대값을 구해줍니다. string을 활용하면 구현이 쉽습니다. 0으로 시작하는 수는 후보에서 빼는 것도 고려해야 합니다. #include #include #include using namespace std; int a, b, res = -1; bool visit[10]; string tc, c; bool..
-
백준 16945번 매직 스퀘어로 변경하기PS 2020. 3. 17. 19:41
https://www.acmicpc.net/problem/16945 16945번: 매직 스퀘어로 변경하기 1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다. 크기가 3×3인 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하려고 한다. 한 칸에 있는 수 a를 b로 변경하는 비용은 |a - b| 이다. 예를 들어, 아래와 같은 경우를 살펴보자. 5 3 4 1 5 8 6 4 2 이 배열의 수를 아래와 같이 변경하면 매직 스퀘어가 되고, 비용은 www.acmicpc.net n이 매우 작으므로 완전 탐색으로 풀 수 있습니다. 순열로 사각형을 만들어서 가중치를 계산하고 최솟값을 저장해나갑니다. ..
-
백준 16951번 블록 놀이PS 2020. 3. 17. 19:38
https://www.acmicpc.net/problem/16951 16951번: 블록 놀이 욱제는 높이가 1인 블록을 매우 많이 가지고 있고, 블록을 쌓아서 탑 N개를 만들었다. 탑은 일렬로 배열했고, 왼쪽에서부터 i번째 탑의 높이는 Ai이다. 욱제가 가장 좋아하는 정수는 K이다. 따라서, 인접한 두 탑의 높이 차이를 K로 만들려고 한다. 즉, Ai+1 - Ai = K를 만족해야 한다. 욱제가 1분 동안 할 수 있는 작업은 탑 하나를 고르고, 탑에 블록을 더 놓아서 높이를 크게 만드는 것 또는 탑에서 블록을 빼서 높이를 작게 만드는 것이다. 인 www.acmicpc.net 완전 탐색 문제입니다. n^2 해도 시간 초과가 나지 않기 때문에 완전 탐색을 할 수 있습니다. 어떤 수를 기준으로 k의 값에 맞추..