Algorithm46 [백준] 1600번 : 말이 되고픈 원숭이 (C++) https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 최단 거리를 구하는 문제이기 때문에 BFS로 구현하였다. 평소 하던대로 BFS 구현은 금방하였지만, 메모리초과 문제가 떠버렸다. 보통 bfs문제에서는 한번 방문한 곳은 지나가지 않도록 로직을 구현했지만, 이 문제에서는 경우에 따라 방문했던 곳이더라도 나이트의 이동 수에 따라 정답 경로가 될수 있다! 따라서, 방문 배열을 2차원이 아닌 나이트의 이동수까지 포함한 3차원 배열로 구현해.. 2021. 9. 6. [백준] 8980번 : 택배 (C++) https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 이 문제에서의 핵심은 택배를 올리면 무조건 목적지에서 내려지기 때문에 무게 맞게 올리는 경우만 고려하면된다. 따라서, 받는 마을과 보내는 마을의 차이가 작고, 택배를 빨리 내릴수록 효율적이기 때문에 받는 마을의 번호를 기준으로 오름차순 정렬한 후 탐색해야한다. 오랜만에 다시 본 문제였는데도 풀이방식이 제대로 생각나지 않았다... 몇번 더 풀어봐야 할 것같다! 문제 풀이 방식은 .. 2021. 9. 5. [백준] 17142번 : 연구소3 (C++) (삼성 SW 기출) https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 브루트포스와 BFS 알고리즘을 사용하여 구현하였다. 맨 처음에 문제를 읽고 구현자체가 어려울 것 같진 않았지만, 테스트 케이스를 돌리다보니 예외처리와 효율성을 고려하는게 빡셌던 것 같다. (덕분에 디버깅만 거의 2시간 한것 같다ㅎㅎ) 애를 먹었던 부분은 "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다." 라는 조건이었다. 좀더 풀어서 설명해보자면, 비활성화된 바이러스.. 2021. 9. 3. [백준] 10164번 : 격자상의 경로 https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 전에 비슷한 경로의 수 구하는 문제를 풀었던 기억이 있어서 DP로 금방 구현하였다. 이 문제에서 핵심은 O로 표시된 좌표를 꼭 지나가야된다는 것이다. 만약, 다음과 같은 사진에서 8을 꼭 지나야 한다면, 8을 기준으로 왼쪽 밑 & 오른쪽 위 좌표들은 계산할 필요도 없고 누적 경로수 계산에 포함시키면 안된다. (Check 함수로 구현하였다.) 전체코드는 아래와 .. 2021. 9. 3. [백준] 10250번 : ACM 호텔 https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net ICPC 예선 기출문제 중 제일 쉬운 문제이다. N이 H로 딱 떨어지는 경우만 유의해주자!! #include using namespace std; int T,H,W,N; int hotel[100][100]; int X, Y; int main() { cin >> T; while (T--) { cin >> H >> W >> N; Y = (N % H==0? H : N % H); X = (N.. 2021. 9. 2. [백준] 1495번 : 기타리스트 https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net DP문제로 저번주 스터디에서 진행했던 5557번 문제와 비슷하였다. 일차원 DP배열과 복사 배열을 통해 현재 턴에 가능한 숫자(인덱스)를 1로 표시하여 이전 데이터 값을 계속 저장하였다. #include #include #include using namespace std; int N, S, M; int n; int v[1001]; //현재 턴에 가능한 볼륨은 .. 2021. 8. 31. 이전 1 ··· 3 4 5 6 7 8 다음
