🔗 문제 14888번: 연산자 끼워넣기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 🖍 풀이 +) 1e9를 이용해 최대, 최소를 표현하는 방법을 배웠다. 완전 탐색으로 싹싹 뒤져보면 된다. 인자로 입력받은 연산자의 개수를 집어넣고 함수가 한번 호출될 때마다 각 연산자로 연산해준다. solve(1, A[0], add, sub, mult, div); 💾 소스 #include long long max=-1e9 , min = 1e9; int N = 0, A[1..

🔗 문제 2307번: 도로검문 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리 www.acmicpc.net 🖍 풀이 문제를 하나씩 뜯어보면 일단 범죄자의 도주 경로와 최소 비용을 구해야 한다. 경로는 양의 가중치가 있는 그래프로 주어진다. 시작 지점과 도착 지점이 주어진다. 두 조건을 보아 다익스트라 기법을 이용해야 한다는 감을 잡았다. 어려웠던 점 최대 지연을 위해서는 모든 도로를 다 빼는 건 시간 초과에다가 틀린 접근이다.( 당ㅇ연함) 도주 경로의 도로를 빼야한다는건 알았는데 어떻게 구현할지 모르겠어서 인터넷의 도움을 받았다. dijkst..

🔗 문제 1976번: 여행 가자 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🖍 풀이 Union-Find로 간단히 풀 수 있는 문제였다. 여행가려는 지점(route)들이 같은 그래프에 속한다면 재방문을 하겠지만 아무튼 갈 수는 있다. 하지만 이어진 곳이 없는 아예 분리된 그래프라면 방문할 수 없다. 그래프 서로소 집합 구하기?.. 바로 유니온 파인드라는 생각이 들어 풀 수 있었다. 1. 연결된 지점을 받을 때마다 merge를 통해 한 그래프로 만들어준다. 한 그래프로 만든다는 건 부모 노드가 같으면 같은 ..

🔗 문제 22868번: 산책 (small) 22868번: 산책 (small) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A, B$가 공백으로 구분되어 주어진다. 정점 $A$와 www.acmicpc.net 🖍 풀이 다익스트라를 이용해서 최소 길이를 찾으려고 했다. 하지만 문제를 읽어보면 모든 간선간의 이동 비용은 1이므로 단순하게 BFS로 풀면 된다. 위 조건 덕분에 정렬 후에 가장 처음 만난 노드로 이동하는 것이 최소 비용이 된다. S → E까지의 최소 이동 비용을 구한다. E → S 까지 최소 이동 비용을 구한다. 1 + 2 의 비용 합산 비용으로 정답을 찾을 수 있다. BFS(S, E)..

🔗 문제 16918번: 봄버맨 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 🖍 풀이 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다. 다음 1초 동안 봄버맨은 아무것도 하지 않는다. 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다. 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다. 3과 4를 반복한다. 폭탄 터지는 조건 설치 후 3초 후 터진다. 터질 때 상하좌우자리도 빈칸..

🔗 문제 https://www.acmicpc.net/problem/13019 13019번: A를 B로 첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다. www.acmicpc.net 🖍 풀이 solve() : A와 B의 구성요소 유무로 가능성 확인 A와 B의 문자열 길이가 같아야 한다. A와 B를 정렬했을 때 서로 같아야 한다. 같은 문자 구성이라면 정렬했을 때 똑같다! 문자열 길이가 짧아서 정렬해도 시간 초과 없음 solve2() A와 B 문자열을 뒤에서부터 같은지 확인하며 다른 문자열이 나오면 ++result 각 A, B의 뒤를 가르키는 포인터 aptr, bptr를 만들고 서로 같을 때까지 aptr을 왼쪽으로 이동..

🔗 문제 16987번: 계란으로 계란치기 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 🖍 풀이 문제 정리 내구도와 무게를 가진 계란 N개가 있다. 왼쪽부터 깨지지 않은 계란을 집어들고 다른 안 깨진 계란을 깰 시도를 한다. 이 때! 내가 깨질 수도 있고 다른 계란이 깨질 수도 있다. 두 계란의 내구도는 상대 계란의 무게만큼 감소한다. 내구도가 음수가 되면 그 계란이 깨진다. 이걸 깰 계란이 없을 때까지 반복한다. 깰 수 있는 계란이 여러 개 있을 때 탐욕 기법을 이용해서 풀어야 하나 고민을 했..

🔗 문제 https://softeer.ai/practice/info.do?idx=1&eid=540&sw_prbl_sbms_sn=158428 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 백준 뿌요뿌요같은 문제인데 아직 시간초과를 해결하지 못 했다. 알고리즘 단톡방에 올렸는데 아무도 대답해주지 않았고 (…) 나처럼 풀었는데 성공한 사람은 꼭 알려주면 좋겠다. 꼭! 🖍 풀이 N*N 구역에서 같은 색깔의 위치로 면적과 몇 대가 있는지 구해야 한다. N*N 구역에서 사라질 수 있는 차량 종류는 여러 가지이므로 DFS를 사용한다. 같은 색깔이 주변에 있는지 탐색하는 것은 BFS를 사용한다. 같은 종류의 차량이 있는 면적을 구해야 하기 때문에 최대 및 최소 좌표와 같은 차량의 ..

🔗 문제 1103번: 게임 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 🖍 풀이 안 올리려다가 나같은 실수한 사람이 있을까봐 풀이를 올려봅니다.. 근데 나밖에 없을 듯 ㅎ DFS에서 DP를 통한 가지치기가 필요한 문제였다. 처음에는 BFS로 풀다가 방향 경로마다 visited를 생성할 수 없다는 걸 깨닫고 DFS로 전환했다. 문제에서 동전이 이동한 후 적혀있는 X만큼 이동하라는 조건이 있다. 근데 나는 dir 방향 한.칸.씩. 이동해서 틀렸다 .. 암만 생각해봐도 왜 틀린지 모르겠어서 질문 올리기 직전에 ..

🔗 문제 16235번: 나무 재테크 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 제한 1 ≤ N ≤ 10 1 ≤ M ≤ N^2 1 ≤ K ≤ 1,000 1 ≤ A[r][c] ≤ 100 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10 입력으로 주어지는 나무의 위치는 모두 서로 다름 🖍 풀이 처음에는 나무를 list에 저장하고 폐사할 경우 -1로 표기하고 해마다 정렬했는데 시간초과였다. 나이 오름차순으로 양분을 먹이려고 정렬을 이용했고, 새로 생기는 나무를 push_front()로 넣어도 시간초과..