🔗 문제 링크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}..
알고리즘 문제 풀이
🔗 문제 링크https://www.acmicpc.net/problem/21610💡 문제 풀이 및 해석시뮬레이션 문제인 만큼 문제의 조건을 그대로 구현하면 된다.이 전에 비가 내린 것을 구분하는 것은 MAP 구조체를 만들어서 isRain으로 판별하였고, next_x,next_y의 99값은 문제의 조건대로 Index를 1부터 쓰기 위함이다. 정확한 방식은 아래와 같다.이동하기 전에, 맵에 isRain을 모두 false로 만들어준다. (처음엔 상관없지만, 한 바퀴 돈 뒤에는 기존에 비가 내렸던 곳의 마킹을 없애주기 위함이다.)방향 * 거리 만큼 이동시킨다.이동시킨 거리를 N으로 나눈 나머지를 구한다. (위치 특정을 위해) 이때, -로 이동하거나 만약 N의 위치에 있다면 0 이하이므로 0 이하이면 N을 더해..
🔗 문제 링크https://www.acmicpc.net/problem/20056💡 문제 풀이 및 해석시뮬레이션 문제인 만큼 문제의 최적화보다는 설명한 그대로 구현해야 한다. 주의할 점만 적어놓겠습니다.파이어볼이 조건에 맞게 이동한다.1-1. 조건대로 이동할 때, 파이어볼이 맵 밖으로 나가는 경우는 반대쪽에서 나오게 설정해야 한다.1-2. 파이어볼이 이동하기 전에 기존에 맵에 저장되어 있던 파이어볼의 정보는 초기화 시켜줘야 한다.이동한 파이어볼은 분열한다.2-1. 분열하면서 주의할 점은 모두 짝수 or 홀수 방향인 것을 정해줘야 한다는 점이다. (따로, 체크를 해야함)2-2. 한 번만 이동해도 분열은 시켜준 뒤에 질량을 측정해야 한다.이 과정을 K번 반복한다.⭐️ 정답 코드 및 설명#include #i..
🔗 문제 링크 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 문제 풀이 및 해석숙련도를 구해야 하는데, 난이도와 시간의 배열이 상당히 크다.숙련도가 어느 정도일지 예상이 안가고, 예제를 보니 1,2,3, ... 이런식으로 가면 최악의 시간 만족도를 충족시킬 수 없다.여기서는 하나씩 체크하는 방식이 아닌 범위를 잡고 좁혀들어가는 이분 탐색 방식이 어울리는 것을 알 수 있다.숙련도와 level에 대해서는 문제에서 설명한 방식 그대로 구현한 것이여서 생략하겠습니다.⭐️ 정답 코드 및 설명#include #include using namespace std;b..
🔗 문제 링크https://www.acmicpc.net/problem/1277💡 문제 풀이 및 해석1과 N이 만나야 한다.두 발전소 사이의 거리(좌표상 거리)가 M미만이면, 두 발전소 사이에는 간선이 있다.이미 이어진 발전소는 길이가 0인 간선이 있다고 생각한다.이제 1에서 시작하는 평범한 bfs문제가 된다. (최적화를 하고 싶다면 다익스트라로 풀어야한다.) vector > > edge(1001); // 발전소, 거리 이 부분을 내부를 vector>> edge(1001) // 거리, 발전소 이와같이 바꾸면 짧은 거리부터 찾아가면서 실제로 더 빠를 것 같다.⭐️ 정답 코드 및 설명#include#include#include#include#define INF 98754321using namespace s..
🔗 문제 링크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..
🔗 문제 링크https://www.acmicpc.net/problem/1083💡 문제 풀이 및 해석배열의 크기가 최대 50이므로 항상 최대로 옮긴다고 해도 50 * 49 / 2 밖에 되지 않는다. 완전탐색, 그리디 방식으로 풀 수 있다는 뜻이다.문제 풀이 순서도는 다음과 같다.2-1. 기회가 끝나거나(S == 0) 모두 정렬(left == right)이 될때까지 반복한다.2-2. 옮길 수 있는 기회만큼(left_index + S) 탐색한다. 단, 탐색이 N을 넘어가는 순간 멈춘다.2-3. 탐색한 범위에서 가장 큰 숫자의 위치와 left_index의 위치를 교환한다. 그만큼 기회를 차감한다.2-4. 교환을 한 뒤에는 다음으로 정렬하는 위치를 옮겨준다. (left_index + 1)⭐️ 정답 코드 및 설..
