본문 바로가기

문제 해결/BOJ117

[백준] 원숭이 스포츠 https://www.acmicpc.net/problem/16438 16438번: 원숭이 스포츠 승민이는 동물원의 원숭이들을 관리하는 사육사입니다. 이 동물원에는 N마리의 원숭이들이 있고 원숭이들에게 1번부터 N번까지 번호를 붙였습니다. 7일간 동물원에서 원숭이들끼리 스포츠 경기 www.acmicpc.net 문제를 제대로 이해하지 못해서 조금 헤맸던 문제입니다. 이 문제의 포인트는 분할정복입니다. 절반으로 쪼개면서 현재 범위에서의 절반과 나머지 절반이 상대팀이 되도록 하면 됩니다. 예를 들어 n = 7일때, AAABBBB -> ABBAABB -> AABABAB순으로 팀을 나누어 주면 최소 한번은 다른 원숭이들과 상대팀이 될 수 있습니다. 7개의 팀 조합을 출력해야하므로 나머지 4개의 조합은 아무렇게나 출.. 2023. 3. 13.
[백준] 괄호 추가하기 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 이 문제의 포인트는 중위 연산을 후위 연산으로 바꾸는 작업과 먼저 계산할 연산자를 정하는 것입니다. 현재 연산자를 괄호로 묶어서 먼저 계산할 경우에는 다음에 나오는 연산자는 먼저 계산할 수 없으므로 다다음 연산자로 넘겨야합니다. 이 문제에서 후위 연산자로 바꾼는 방법은 숫자는 나오는 순서대로 list에 넣어주고 연산자인 경우 현재 연산자가 먼저 계산되어야하면 스택에 먼저 계산되면 .. 2023. 3. 11.
[백준] 피리 부는 사나이 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 이 문제의 핵심은 DFS를 통해 싸이클을 찾는 것 그리고 다른 싸이클에 포함이 되는지 여부를 찾는 것입니다. 방문되지 않은 위치를 시작으로 DFS로 탐색하다가 방문한 위치를 다시 방문하게 되었을 때 값이 -1이면 새로운 싸이클을 만난 것이고 0보다 큰 값이면 기존에 탐색된 다른 싸이클에 포함되는 것을 의미합니다. 각각의 싸이클에 SAFE ZONE을 설치하면 되므.. 2023. 3. 10.
[백준] 모양 만들기 https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net Flood Fill을 활용하여 풀이하였습니다. 각각의 그룹을 기록해주고 해당 그룹과 연결될 수 있는 빈칸들에 현재 그룹들을 set에 넣어줍니다. 그 다음 2차원 배열을 돌면서 현재가 빈칸이고 다른 그룹에 연결될 수 있는 후보 그룹들이 set에 저장되어 있으므로 해당 set에 저장되어 있는 후보 그룹들의 면적을 더해주면 현재 칸을 변경했을 때 얻을 수 있는 모양의 최대 크기가 됩니다. i.. 2023. 3. 9.
[백준] 서울 지하철 2호선 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net DFS를 활용하여 풀이한 문제입니다. 먼저, 싸이클을 찾기 위해 DFS가 필요로 한데 아무 정점을 시작으로 DFS 진행하는데 이전 노드로만 되돌아가지 않게 진행을 합니다. 이렇게 하면 한쪽 방향으로만 DFS가 가능하게 됩니다. 한쪽 방향으로 탐색하다 방문한 정점을 또 만나게 된다면 그 정점이 싸이클의 시작정점이 되게 됩니다. 시작 정점을 찾은 순간 flag에 싸이클의 시.. 2023. 3. 8.
[백준] 임계경로 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 골드 2를 찍기 위해 친구가 추천해준 문제를 풀어보았습니다. 위상정렬을 사용하여 해결한 문제입니다. 일방향 통행, 싸이클이 없다는 두개의 조건을 보고 위상정렬이 떠올랐습니다. 위상정렬을 하면서 현재 노드까지의 최대거리를 갱신해줍니다. 그리고 최대거리로 갱신해준 노드들을 저장해둡니다. 그 다음으로는 도착점을 시작으로 현재 노드들을 최대거리로 갱신해준 노드들을 역으로 탐색해.. 2023. 3. 7.
[백준] 움직이는 미로 탈출 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 라운드 방식으로 진행하는 BFS로 풀이하였습니다. 욱제가 각 라운드마다 움직일 수 있는 모든 위치를 BFS를 통해 저장해둡니다. 그 다음 위치를 저장해둔 벽의 위치를 라운드마다 한칸씩 밑으로 내려주면 됩니다. 만약 BFS를 통해 오른쪽 끝 위치에 도달할 수 있다면 탈출이 가능합니다. 이 문제의 포인트는 2가지입니다. 욱제가 제자리에 계속 있을 수 있다는 점, 벽을 움직일 때 행이 더 큰.. 2023. 3. 7.
[백준] 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 에라토스테네스의 체와 누적합을 활용하는 문제입니다. 먼저, 에라토스테네스의 체를 통해 n보다 작은 모든 소수를 구해줍니다. 그 다음 소수들을 누적합을 해가면서 check라는 set에 저장을 해줍니다. 현재까지의 누적합을 저장하면서 동시에 현재까지의 누적합에 n을 뺐을 때의 값이 check set에 들어있다면 연속된 소수의 합으로 만들 수 있는 경우가 됩니다. import sys input = sys.stdin.readline n = int(input()) check = set() def era(num): isPrim.. 2023. 3. 6.
[백준] 배열 B의 값 https://www.acmicpc.net/problem/16971 16971번: 배열 B의 값 첫째 줄에 배열 A의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 배열의 원소가 주어진다. 배열은 정수로만 이루어져 있다. www.acmicpc.net 각각의 배열의 원소의 위치에 따라서 배열 B에 포함되는 횟수를 표시해보면 다음과 같습니다. 1 2 2 2 1 2 4 4 4 2 2 4 4 4 2 1 2 2 2 1 A[0][0]에 위치한 요소는 배열 B를 만드는데 한번만 사용됩니다. 반면 A[1][1]은 4번 사용됩니다. 그리고 다음과 같은 규칙을 찾을 수 있습니다. 행과 열의 처음과 마지막은 1 2....2 1과 같은 패턴을 띄고 나머지 행과 열은 2 4....4 2와 같은 패턴을 보입니다. 즉, 행과.. 2023. 3. 5.

티스토리툴바