🔗 문제 링크https://www.acmicpc.net/problem/20057💡 문제 풀이 및 해석문제의 핵심은 일정 비율로 모래가 흩날리는 것인데, 기존에 BFS 문제에서 next를 정해두고 상하좌우로 이동하는 것을 조금 늘렸다고 생각하면 된다. 해당 코드는 다음과 같다. 퍼지는 것은 9개인데, 왜 10개냐면 마지막은 문제에서 설명상 알파의 위치이다. 그리고 퍼지는 위치에 맞게 percent도 정해놨다.int next_x[][10] = { {0, -1, 1, -2, -1, 1, 2, -1, 1, 0}, {2, 1, 1, 0, 0, 0, 0, -1, -1, 1}, {0, -1, 1, -2, -1, 1, 2, -1, 1, 0}, {-2, -1, -1, 0, 0, 0, 0, 1, 1, -1}..
G3
🔗 문제 링크https://www.acmicpc.net/problem/17142💡 문제 풀이 및 해석간단하다. 모든 칸은 감염시켜야 한다.정해진 갯수를 골라서 모든 칸을 감염시키는데 걸리는 시간이 최소가 되게 해야한다. 단, 감염시킬 수 없는 칸이 존재한다면 -1을 반환한다.애먹은 점이 이 조건이다. 바이러스를 활성화 시켰을 때, 비활성 바이러스도 있는 것으로 간주한다. 이는 비활성 바이러스가 있는 칸을 감염시키며 나아갈 수는 있지만, 감염시키지 않아도 그 칸은 감염되어 있는 것으로 간주한다는 뜻이다. 이를 설명하는 설명 예시이다.⭐️ 정답 코드 및 설명#include#include#include#include#define INF 987654321using namespace std;int N, M, ..
🔗 문제 링크https://www.acmicpc.net/problem/16236💡 문제 풀이 및 해석아기 상어는 매초 상하좌우로 1칸을 이동할 수 있다. 단, 자신보다 큰 물고기가 있는 칸은 갈 수 없다.아기 상어는 자신보다 작은 물고기를 잡아먹을 수 있다.아기 상어는 가장 가까운 물고기를 잡아먹으러 간다. 단, 거리가 같다면 가장 위쪽 그리고 가장 왼쪽에 있는 물고기를 잡아먹으러 간다.잡아먹으러 갈 수 있는 물고기가 없다면, 엄마를 부른다.(끝난다)위 조건들을 순서대로 BFS방식으로 코드를 짜면 된다. 3번의 조건은 가장 가까운 물고기가 2마리 이상이라면 모든 물고기 중 가장 위쪽에 있고 가장 왼쪽에 있는 물고기를 판별하여 먹으러가게하면 된다.⭐️ 정답 코드 및 설명#include#include#i..
🔗 문제 링크 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 💡 문제 풀이 및 해석 일단, 보자마자 비싼 강의를 최대한 많이 들어야 한다는 것을 알 수 있다. 여기서 어떻게 들어야 할 것인가가 중요하다. 여기서 day로 정렬해서 한다면, 문제가 발생한다. 예를 들어서, 같은날 비싼 2개의 강의가 있을 때, 전날 강의를 버리고 그 다음날까지 유예기간이 있는 강의를 들을 수가 없기 때문이다. 여기서 해결방법으로는 아래와 같다. 가장 비싼 강의로 내림차순으로 정렬한다. 유예기간..
🔗 문제 링크 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 💡 문제 풀이 및 해석 첫 번째로 친구들의 집합을 만드는 것이 중요했다. 친구관계도를 만들기 위해서 myFriend를 이용해서 i번의 친구를 vector로 저장한다. 그럼 i번의 친구들의 친구들을 다시 모두 탐색한다. 단, 아직 친구 그룹이 형성되어 있다면 찾지 않는다. (이미 같은 그룹이기 때문) 1N 번의 아이를 23번 과정을 반복해서 모든 그룹을 만들어준다. ..
🔗 문제 링크 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 💡 문제 풀이 및 해석 경우의 수가 크지 않으므로 BruteForce로 풀 수 있을 것이라 생각했다. 일단, 0개를 설치한 경우는 반드시 조건에 성립하므로 예외처리해 준다. (안 해줘도 상관없다.) DFS 방식으로 사다리를 설치하면 브루트 포스하게 풀 수 있다. (이게 최선인지는 아직 모르겠다.) 설치할 다리의 개수를 모두 설치했을 때, 이 방식이 정답인지 확인하고 아니면 다음 경우의 수로 넘어간다. 정답이 나올 때까지 3번-4번을 반복한다. 모두..
🔗 문제 링크 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net 💡 문제 풀이 및 해석 만약 0 만 살 수 있거나 N == 1인 경우 방번호는 0으로 고정이다. 가장 큰 수는 어떤 수일까? 2-1. 자릿수가 긴 수이다. 2-2. 자릿수가 같다면, 앞에서부터 비교할 때, 앞자리의 수가 큰 수이다. 먼저 0을 제외한 가장 코스트가 낮은 숫자를 찾아 맨 앞자리에 넣는다. 0과 비교해서 더 낮은 코스트인 수를 뒤에 최대한 많이 붙인다. 가장 앞자리부터 9 ~ 앞자리의수 까지 비교해서 교체할 수 있으면 교체한다. ⭐️ 정답 코드 및 설명 #include #include using namesp..
🔗 문제 링크 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 💡 문제 풀이 및 해석 점프와 걷기가 있다. 만약, 점프가 걷기보다 느리다면, 굳이 점프할 필요없이 걷기로만 이동하면 된다. 충분히 가까워 진 순간은 "점프 2번으로 갈 수 있는 거리" > "현재 위치에서 목적지까지의 거리" 이다. 2번 지점에서는 2가지 선택지가 있다. 3-1. 조금 돌아서 가는 점프 2번의 거리 (최단 경로가 아닌, ^ 모양으로 위로 조금이동하고 아래로 이동하는 방법) 3-2. 목적지를 점프 경로안에 넣고, 남은 거..
