백준31 [BOJ]16954 - 움직이는 미로 탈출(그래프 탐색 - bfs, dfs) https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net - 좀 특이한 그래프 탐색 문제여서 기록해둔다. 미로벽이 아래 방향으로 움직이는 경우의 수를 따로 메모리를 할당해서 저장하는 것이 아니고 시간이 1초 지날 때마다 아래 방향으로 1씩 움직이는 것을 이용해서 지금 캐릭터의 있는 위치의 t초 전, t+1초 전의 위치가 벽인지를 체크하는 방식으로 짤 수 있다. 이를 배열로 표현하면 a[nx-t][ny], a[nx-t-1][ny] 가 벽인지를 .. 2021. 6. 29. 8980 - 택배(greedy) www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net - 운반거리가 짧은 구간. 즉 도착지가 가까운 순으로 배송정보를 정렬하고, 지나가는 마을마다 담을 수 있는 박스의 최대치는 답에 더해나가는 그리디 방식으로 접근했다. #include #include #include using namespace std; // 도착지가 가까운 순으로 배송정보를 정렬하고 // 트럭이 지나가는 마을마다 트럭이 상자를 실을 수 있는 최대치를 모두 더한다 // 경로상에.. 2021. 4. 1. [boj]15723 - n단논법(Floyd Warshall, string 입출력) www.acmicpc.net/problem/15723 15723번: n단 논법 m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다. www.acmicpc.net - 플로이드 와샬 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제이다. - 플로이드 와샬을 통해서 입력을 통해 주어진 논증 외에도 2~n단 논법을 통해서 징검다리 식으로 증명할 수 있는 논증에 대해서 차례차례 DP 스타일로 증명해 나갈 수 있다. - string 전체를 입력으로 받을 때 getline(cin, string)을 쓰는데 이전에 cin으로 입력을 받았다면 꼭 flushing을 해서 버퍼에 남아있는 '\n'을 제거 해줘야한.. 2021. 4. 1. [boj] 8980 - 택배(greedy) www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net - 그리디 방식으로 접근했다. 출발지에서 도착지가 가까운 도시의 박스를 옮기는 것이 최적의 해를 구할 수 있다. - 도착지가 가까운 순으로 배송정보를 정렬하고, 트럭이 지나가는 마을마다 트럭이 상자를 실을 수 있는 최대치를 모두 더한다 - 경로상에서 트럭이 실을 수 있는 최대치는 (최대용량 - 이미 실고 있는 박스) 이다 #include #include #include using namesp.. 2021. 3. 29. 이전 1 ··· 3 4 5 6 7 8 다음
