https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제조건 톱니바퀴 4개, S극(1), N극(0) 존재 각 톱니바퀴가 맞닿아있는 부분이 극이 다르면 다른 방향으로 회전, 같으면 맞닿아있는 톱니바퀴는 회전X 12시방향부터 시계방향순서대로 8개의 톱니에 S, N 주어짐 돌리는 과정을 모두 수행한뒤, 최종적인 톱니바퀴 상태에서 4개의 12시방향에 있는 S들의 합 문제 파악하는데 30분 정도 걸린거같다. 역시나 문제는 복잡하고 풀이 방법은 쉽겠지,,..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제조건 n명의 사람을 각각 n/2 명씩 두팀으로 나눈다. 한 팀의 능력치는 (i, j) 가 같은 팀이라면 map[i][j] + map[j][i]로 나타내고, 같은 팀의 사람들의 능력치를 모두더한다. 두 팀의 능력치 차이의 최솟값은? 접근방법 보자마자 입력값도 작고, 최솟값을 구하기 위해 모든 경우의 수를 Brute Force로 탐색하면 되는 거 아닌가? 생각이 들었고, DFS로 모든 경우의 수에 대해서 탐색했다. 너..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제조건 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우, 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우, 반..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제조건 벽(1)을 무조건 3개를 세운다. 벽은 바이러스(2)가 퍼져 나가는걸 막아준다. 안전영역(0)의 크기가 최댓값은 얼마인가? 접근방법 애초에 입력이 8이하로 너무 작아서 진짜 내 맘대로 구현할 수 있는 문제였다. 처음에는 최대한 깔끔하게 로직을 짤 수 없을까란 생각이 계속 들었지만, 그리디도 아니고, 어느 알고리즘도 적용할 수 없었다. 여기에 시간을 좀 많이 쏟은것 같다. 단순하게 문제조건만 맞춘다면 ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제조건 퇴사 전까지 상담을해서 얻을수 있는 최대 수익을 구하라 단순히 구현 + dp 문제였다. dp[i] : i일까지의 상담중에서 최대 수익 값 완전탐색을 진행하면서 상담에 걸리는 일수가 퇴사 전일때, 구하고자 하는 일자의 수익과, 지금까지의 수익 + 구하고자 하는 일자까지 상담하는 수익을 비교해서 최댓값을 갱신시켜줬다. 소스코드 #include #include using namespace std; int n, t[16], p[16], dp[16]; int main(){ cin >> n; for (int i = 0; i < n; i..

https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 문제조건 n개의 시험장 각 시험장의 응시자 수(a) 총감독관이 감시할수 있는 수(b), 부감독관이 감시할수 있는 수(c) 총감독관은 시험장마다 오직 1명만 가능 너무 쉽게 생각했는데, 처음부터 틀려버렸다. 예외 조건이라고는 총감독관 혼자서 응시자를 모두 감시할 수있을경우에 대한 로직만 처리하면 될 줄 알았는데, 뭐가 문제인지 몰랐다. 생각해..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제조건 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 접근방법 먼저 자료구조 queue가 떠올랐다. 사과가 없다면 꼬리부분을 계속삭제해야하므로,..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제조건 N x M 크기의 보드가있다. 빨간공과, 파란공이 각 하나씩 있다.(위치 주어짐) 공을 내보낼수있는 구멍이 하나 있다.(위치 주어짐) 보드를 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다. 이 동작만으로 공을 움직여서 빨간공만 구멍으로 빼야한다. 빨간공, 파란공은 항상 같이..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제조건 주식하나 사고, 팔고, 아무것도 안하는 것중 하나만 할 수 있다. 각 날마다의 주가가 주어지고, 조건 1 을 반복하면서 최대이익을 구한다. 이 문제는 예시로 시작하는 것이 편할거 같다고 생각한다. ex) 날 별로 주가가 3, 5, 9일 때 : 3, 5 두 날 전부 주식을 사고, 9일때 주식을 팔면된다 산금액 : 8(3x1 + 5x1) 판금액 : 18(9 x 2) 최대이익 : ..

https://www.acmicpc.net/problem/20006 20006번: 랭킹전 대기열 모든 생성된 방에 대해서 게임의 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력한다. 시작 유무와 플레이어의 정보들은 줄 바꿈으로 구분되며 레벨과 아이디는 한 줄에서 공백 www.acmicpc.net 문제조건 플레이어가 입장을 신청하였을 때 매칭이 가능한 방이 없다면 새로운 방을 생성하고 입장시킨다. 이떄 해당 방에는 처음 입장한 플레이어의 레벨을 기준으로 -10부터 +10까지 입장 가능하다. 입장 가능한 방이 있다면 입장시킨 후 방의 정원이 모두 찰 때까지 대기시킨다. 이때 입장이 가능한 방이 여러 개라면 먼저 생성된 방에 입장한다. 방의 정원이 모두 차면 게임을 시작시킨다. 먼저 입력을 받으면..