https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 백준에서 bfs를 많이 연습했다면 크게 어렵지는 않았을 거라 생각한다. 문제를 풀이해보겠다! 우선, 백조의 위치를 vector에 저장한다. 그리고 물과 백조의 위치를 wq라는 큐에 저장해놓는다. 백조의 위치를 물의 위치와 같이 저장하는 이유는, 백조도 물에 떠있기 때문이다!! 만약 백조가 X에 둘러 쌓여져 있는 상황에 처할 경우, 다음 날이 되면 물의 영향으로 길이 생..
주사위는 6개의 면을 가진다 -> 크기 6의 배열로 관리 주사위는 앞,뒤,좌,우로 구를 때 마다 면이 바뀐다 ex) 우로 구르면, 오른쪽면이 바닥면이 된다. => 배열의 인덱스마다 주사위의 한 면씩 매칭시켜준다. 그리고 주사위가 특정 방향으로 구를 때마다, 바뀐 것을 원래 설정해놓은(= 매칭시켜놓은) 인덱스로 설정해주면 된다. 자세한 내용은 주석에 달아놓았다. 문제 난이도치고는 쉽게 풀었다. 중간에 풀면서 바뀌는 상태를 원형 큐로 관리할 수 있지않을까 생각도 해보았는데, 시간있을 때 도전해봐야겠다 #include #include #include #include using namespace std; int n,m,x,y,k,order; int board[21][21]; int bottom = 5; in..
이 문제는 도저히 모르겠어서 구글링 했다.. 다른 사람들의 풀이를 봐도 도저히 모르겠어서 머리 꽁꽁 싸매고 고민하던 중! 드디어 깨달아버렸다.. 너무 감격한 나머지 흔적을 남기고자 한다. 예를 들어 내가 5457번 채널로 가고 싶다고 하자, 현재 나는 100번 채널을 시청 중이다. | 5457 - 100 | 을 통해 순수 + - 만 이용해 원하는 채널로 가기 위한 횟수를 구한다. 그런 다음 0번 채널부터 1,000,000번 채널까지 반복한다. (인덱스는 i로 설정) 문제에서 주어진 건 500,000이지만 위에서 감소하면서 내려오는 경우도 있으니 1,000,000번까지 고려해준다 i번 채널로 이동 가능하면, i번 채널로 가는데 필요한 버튼 누르는 횟수를 계산하여 반환해주고 i번 채널로 이동 불가능하면 그냥..
문제를 찾아보면 알겠지만 N개의 마을에 사는 N명의 학생들이 특정한 한 집에 모여 파티를 하고, 다시 집으로 돌아가는데 드는 비용 중 최대 비용을 구하는 것이다. 다익스트라 코드는 기본적인 코드이며, 우선 특정한 한 집(코드에서는 x)에서 각각 학생들의 집까지 거리를 구하기 위해 start를 x로 하고 다익스트라를 통해 최소신장트리를 구한다. 그리고 배열 하나를 만들어서 x마을부터 각 학생들의 집(1,2,...,N)까지의 최소거리를 더한다. 다시 for문을 반복하여 각각의 학생들(i번째 학생들)에 대해 다익스트라를 실행 한 뒤, 특정한 집(변수 x)에 도달하기까지 걸리는 최소비용을 구해서 배열에 더해준다. 최소비용중 최대를 구해야하므로 변수 res를 하나 두어 최대를 뽑아낸다. res를 처음에 0으로 초..
시뮬레이션 문제를 풀 땐, 문제에 나와있는 조건대로 잘 따라 풀어주어야 한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 0. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 1. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 2. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 우선, 만약 벽 또는 자기자신의 몸과 만난다면? break하고 게임을 종료시키면 된다. 그 다음엔 사과가 있는 경우와 없는 경우로 나누어 조건식을 세운 다음 문제를 풀면 된다. 방향 전환이 조금 까다로운데, 문제 처음에..
#include using namespace std; int dp[1000001]; int min(int a, int b) { if (a > b) return b; return a; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; dp[1] = 0; for (int i = 2; i
