hades

보호되어 있는 글입니다.

보호되어 있는 글입니다.

🥅 문제https://www.acmicpc.net/problem/2579 🔍 설계시작점은 계단에 포함되지 않는다. 한 계단에서는 다음 계단이나 다다음 계단으로 이동할 수 있다.마지막 계단은 무조건 밟아야 한다. 재귀로 구현한다면, 계단의 개수가 300개이므로, O(2^300)이므로 시간 초과가 발생할 것이다. 어떤 계단까지의 점수 중 최댓값은 전 계단까지의 점수+어떤 계단의 점수와 전전 계단까지의 점수+어떤 계단의 점수를 비교하여 구할 수 있다. 예를 들어, 5번째 계단까지의 총 점수를 구하는데, 3번째와 4번째 계단의 점수가 활용된다는 것이다. 즉, 다이나믹 프로그래밍을 이용하여 구할 수 있다.  어떤 계단까지의 점수를 단순히 하나로 저장하면 안된다. 다음 계단에서 점수를 계산할 때, 어떤 계단까지..

🥅 문제https://www.acmicpc.net/problem/2178 🔍 설계미로가 주어지고, 1인 칸 중에서 인접한 칸으로 이동할 수 있다는 것에서 BFS라는 것을 파악했다. 지나야하는 최소 칸을 구해야 하기 때문에, 각 칸마다 그 칸으로 오기까지 이동한 총 칸의 수를 dp에 저장한다. 어떤 칸으로 이동했을 때, 이동하기 전 칸이 저장한 값+1이 이동한 칸까지 이동한 총 칸의 수이다. 이 값보다 이미 저장하고 있는 값이 작다면, 최소 칸을 구할 수 없으므로, 큐에 담지 않는다. 👊 풀이#include #include #include #include #include using namespace std; int n, m;int dx[] = {-1,1,0,0};int dy[] = {0,0,-1,1}..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

🥅 문제https://www.acmicpc.net/problem/1931 🔍 설계회의실 하나에 최대로 몇 개의 회의가 가능한지 구해야 한다. 회의의 시작 시각이 빠른 것을 먼저 고려하기 위해서 첫 번째로 회의의 시작 시각, 두 번째로 회의의 종료 시각을 기준으로 하여 오름차순으로 값을 꺼낼 수 있는 우선순위 큐를 만들었다. 고려해야할 것은 (시작 시각, 종료 시각)이라고 할 때, (0, 6) 대신 (1, 3) (3, 6)이 결과값을 도출하는 회의의 개수에 포함된다. 시작 시각이 가장 빠른 회의의 시작 시각이 다음 회의가 시작 가능한 시각(next_available_time) 보다 뒤라면, 할 수 있는 회의가 한 개 증가한다. 그리고, next_available_time을 그 회의의 종료 시각으로 갱신..

🥅 문제https://www.acmicpc.net/problem/1764 🔍 설계듣지도 못하고, 보지도 못한 사람의 이름을 찾아야 한다. 듣지도 못한 사람을 우선 저장하고, 보지도 못한 사람이 저장한 사람 중에 있는지 확인하면 된다.   문자열을 키로 저장할 수 있는 맵을 이용하여 듣지도 못한 사람을 먼저 저장하고, 보지도 못한 사람을 맵에서 find하여 있다면 결과 벡터에 저장한다. 저장된 사람을 오름차순으로 정렬 후 출력한다.  👊 풀이#include #include #include #include #include using namespace std; int n, m;string name;map mm;vector result;int main() { cin.tie(NULL); ios_base::s..

보호되어 있는 글입니다.

🥅 문제https://www.acmicpc.net/problem/1697 🔍 설계현재 위치를 x라고 할 때, 그 위치에서 +1, -1, *2의 위치로 이동할 수 있으므로, 큐에서 현재 위치를 꺼내 매 초마다 이동할 수 있는 새로운 위치를 갱신한다.   큐가 빌 때까지 하는데, 어떤 초에 놓여져 있는 위치로부터 다음 초에 이동할 위치 얻어내는 과정에서 이동하기 전 size를 저장하고, 반복문을 사용하였다.  다음 초에 이동할 수 있는 위치의 범위를 반드시 확인해야 한다.  어떤 위치에 이미 이동했고, 그로 인해 새로운 위치를 얻어냈는데, 나중에 또 방문한다면 중복이 일어나 메모리 초과, 시간 초과가 발생하므로 어떤 위치에 이동한 시각을 visited에 저장하여 저장된 시각보다 도착한 시각이 크다면 큐에..