🔗 문제 링크 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 💡 문제 풀이 및 해석 먼저 가로, 세로 조건이 8이하이다. 따라서 전체 칸은 64칸이다. 3개의 모든 기둥을 박아야 하므로 64개의 칸 중에서 3개를 선택하는 조합, 그리고 그 상태에서 BFS를 진행한다고 하면, 최대 $64\times63\times62\over3\times2\times1$ $\times64 = 2,666,496$ 이 된다. 이를 토대로 완전탐색을 진행하기로 하였다. 먼저 64개의 칸중 3개의 칸을 조합으로 구성한다. 그 구성이 실제로 가능하면..
알고리즘 문제 풀이
🔗 문제 링크 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 💡 문제 풀이 및 해석 N이 최대 20이고, 교실의 크기는 20*20 이므로 400이다. 모든 칸에서 인접한 칸을 조사해도 400*4 밖에되지 않는다. 학생들의 배치는 BruteForce로 하고 만족도 또한 BruteForce로 해도 10만번으로 끝낼 수 있다. 코드에 대한 자세한 설명은 주석에 달아뒀다. ⭐️ 정답 코드 및 설명 #include #include #include #include #include using namespace ..
🔗 문제 링크 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 💡 문제 풀이 및 해석 공기가 한 번에 다 퍼지게 해야된다. 따라서 모든칸에서 퍼지게 해야되므로 모든 칸에서 로직이 작동되게 해야된다. 현재 칸에서 퍼지게하고, 다음칸을 퍼지게하면, 이미 먼지가 퍼진 상태에서 로직이 실행되므로 먼지가 퍼지는 배열을 따로 만들어줘야 한다. 먼지가 다 퍼지면, 공기가 순환되게 해야된다. 이 때, 공기청정기로 들어오는 방향으로 1칸씩 땡기고, 공기청정기에서 나오는 칸만 0으로 처리해주면 된다. 마지막으로 모든 칸의 먼지..
🔗 문제 링크 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 💡 문제 풀이 및 해석 문제의 전체적인 흐름은 '현재 칸 청소' 반시계 90도로 회전하면서 청소할 있을 경우 이동 한 바퀴 돌고도 청소할 공간이 없다면 후진한다. 후진할 공간이 없다면 작동을 멈춘다. ⭐️ 정답 코드 및 설명 #include using namespace std; int N, M, r, c, d; int dir[] = { 0,3,2,1 }; int next_x[] = { 0,1,0,-1..
🔗 문제 링크 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 💡 문제 풀이 및 해석 경로가 겹치지 않는 경우만 계산하면 된다. 이 경우보다는 겹칠 때, 이동을 끝내는게 구현에 용이해 보였다. 매번 bool 배열을 파라미터로 받으면 시간초과가 날 수도 있을 것 같아서 전역변수로 방문여부를 체크했다. '1 - 단순하지 않은 경로'로 구현 ⭐️ 정답 코드 및 설명 #include using namespace std; int n; double E, W, S, N; double answer = 0; bool is..
🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 및 해석 1. 10000명정도의 사람이 들어올 수 있는데, 각각의 사람이 판매 금액의 10%씩 추천인에게 주어야한다. 2. 여기서 12원일때 1.2원이 되는게 아니고 1원씩 올라가는 것을 보니 int / 10 형식으로 올리는 것 같다. 3. 단, A->B 에서 12원을 주고, C->B 에서 18원을 줄 때, 따로따로 주면 B->D 에서 각각 1원씩 주지만, 이 계산을 한번에 진행한다면 ( 12+18 ) / 10 = 3 이 되므로 각각 계산해야 한다. 4. 0원일 때, 추천인이 없을..
🔗 문제 링크 1379번: 강의실 2 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 💡 문제 풀이 및 해석 최대한 적은 강의실 사용 종료 시간과 시작 시간이 겹치는건 가능 따라서 가장 빨리 끝나는 강의 기준으로 가장 빨리 시작하는 강의가 이어서 할 수 있다면 새로운 강의실을 배정할 필요는 없다. ⭐️ 정답 코드 및 설명 #include #include #include #include #define endl "\n" using namespace std; int N; priority_queue q; // 끝나는 시간..
🔗 문제 링크 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 💡 문제 풀이 및 해석 1. 입력이 50개라는 제한이 있었다. 2. 2초라는 50개에 비한 비교적 널널한 시간제한이 있었다. 3. 위의 두가지 조건을 고려하여 brute force로 진행. ⭐️ 정답 코드 및 설명 #include #include #include using namespace std; int N; int cnt[50]; vector building; void input() { cin >> N; for (int i = 0; i < N;..
