while(1) 작심삼일();

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이) 백트래킹으로 현재 위치(0)에서 가능한 경우의 수를 구하고 가능하면 해당 숫자를 넣고 dfs를 돌리고 다시 나왔을 때는 다른 수를 넣어야하므로 0으로 다시 처리를 해두었다. 만들 수 있는 경우의 수가 여럿있어서(?) 기재조건에 exit(0) - 정상종료를 시키지 않았더니 틀렸다고 채점되었다(..? 시간초과가 아닌..) 여튼.. 그래서 넣어두었다. #include #include using ..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이) 1. 분리됐는지 확인한다. (dfs) 2. queue에 담아서 빙산을 녹인다. (그냥 녹이면 옆 빙산이 잘못 녹는다) 3. 맵에 녹일 게 있는지 확인한다. 위 3과정을 반복하면 된다. 2 -> 3 -> 1 순으로 제출했다가 이미 나눠져있는 반례를 확인하고 수정하였다. #include #include using namespace std; int N, M, ans, result = 0, ..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이) 다수가 그렇듯 직전문제와 비슷한 위상정렬이라 생각했고 접근했다. inDegree를 하나씩 내리면서 가지고 있던 back값들을 앞으로 더해주고 마지막에 1~N까지 돌면서 back[i] + front[i] == N - 1까지를 접근을 했는데 위상정렬로는 해결할 수 없었던 문제였다. 플로이드 와샬로 해결할 수 있었고, i -> j에 대한 거쳐가는 모든 정점을 고려해서 각 정점들의 모든 관계를 업데..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이) 1. 궁수를 놓을 수 있는 위치를 dfs를 통해 조합을 구성한다. 2. 맵이 비었으면 게임이 종료시킨다. 3. 궁수들이 세팅이 되었다면 각 궁수들마다 잡을 적들을 세팅해서 queue에 넣어준다. (여러 궁수가 한 적을 노릴 수도 있어서) 4. 큐를 비우면서 적이면 죽인다. 5. 적을 이동시킨다. #include #include using namespace std; int N, M, D, ans = 0..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이) 음의 간선이 존재하는 경우 벨만포드 알고리즘을 사용해야 했다. 다익스트라 알고리즘에 음의 간선을 적용하게 된다면 최소 비용을 찾다보니 사이클에 빠지게 되고, 결국 정점에 도달할 수 없게 된다. 벨만포드는 출발점에서 도착점까지 결국 V - 1개의 간선만 사용되는게 최단경로라는 점을 이용한 알고리즘이기 때문에 간선이 V - 1개를 넘..

http://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 풀이) 어느 중량이 통과 가능할 지 모르기 때문에 입력받은 중량 중 가장 큰 무게를 저장해두고, 이분탐색을 이용하였다. mid = (left + right) / 2로 무게를 정한다음 bfs를 돌려서 해당 무게가 가능한지 돌려보고 가능하다면 left = mid + 1, right = mid - 1로 범위를 좁혀나가는 방식으로 해결하였다. #include..