hades

🥅 문제https://www.acmicpc.net/problem/7569 🔍 설계익은 토마토가 인접한 익지 않은 토마토에 영향을 준다. BFS 문제라는 것을 알아차릴 수 있다. 처음에 익은 토마토를 큐에 담는다. 날마다 익은 토마토의 영향력을 행사한다. 주변의 토마토가 익지 않은 토마토라면, 익게 만들고, 그 토마토를 큐에 담는다. 주의해야할 것은 날마다 익은 토마토의 영향력을 행사했는데, 영향을 받은 토마토가 없다면, day를 증가시키면 안된다. 👊 풀이#include #include using namespace std;int dh[] = { -1,1,0,0,0,0 };int dl[] = { 0,0,0,0, -1,1 };int dw[] = { 0,0,-1,1,0,0 };int m, n, h, da..

🥅 문제https://www.acmicpc.net/problem/5525 🔍 설계IOIOIOIOI에서 n=1이라면 4, n=2라면 3, n=3이라면 2, n=4라면 1이 된다.IOI의 개수가 4이므로, 결과값은 IOI 개수 + 1 - n이다. 👊 풀이#include #include #include using namespace std;int n, m;string s;int result = 0;int main(void){ cin >> n >> m >> s; for (int i = 0; i 0){ result += count+1-n; } } cout  📝 메모IOI의 개수보다 n이 큰 경우, 음수가 되기 때문에 조건을 추가해야 한다.

🥅 문제https://www.acmicpc.net/problem/5430 🔍 설계R이면 뒤집고, D이면 맨 앞에 있는 숫자를 삭제해야 하는데, R일 때마다 뒤집는데 시간이 많이 소요된다.따라서, 앞 뒤에서 삭제를 할 수 있는 덱을 이용한다. 입력에 괄호와 쉼표가 포함되어 입력되므로, 조건문을 통해 숫자들을 담아야 한다.[ 라면 추가적인 처리를 할 필요가 없다., 또는 ] 라면 숫자를 덱에 담는다.이외라면, 숫자를 구성한다. 출력, 삭제할 때 앞에서부터 할지 뒤에서부터 할지 결정하기 위해 sign이라는 변수를 설정하였다. 0이면 앞에서부터, 1이면 뒤에서부터, 2이면 비어있는데 삭제해서 error인 경우이다. 👊 풀이#include #include #include using namespace std;..

🥅 문제https://www.acmicpc.net/problem/2667 🔍 설계1로 구성된 칸들이 서로 연결된 것을 하나의 단지라고 한다는 것에서 BFS임을 알아차릴 수 있다. 지도의 칸에 대하여 반복문을 수행하고, 1인 칸이 있으면, 그 칸이 단지를 구성하는 시작점이다. 따라서, 단지 개수를 1 증가시키고, BFS를 실행하여 단지를 구성하고 넓이를 반환한다. 반환한 넓이는 오름차순 우선순위 큐에 담아 출력하였다. 👊 풀이#include #include #include #include using namespace std;int dx[] = {-1,1,0,0};int dy[] = {0,0,-1,1};int n, count = 0;string row;vector> mapp(25, vector(25))..

🥅 문제https://www.acmicpc.net/problem/2630 🔍 설계현재 색종이의 모든 칸의 색이 같지 않으면 4등분해 나가는 문제이다. 재귀로 해결할 때의 시간 복잡도를 계산해보면, O(2^7*2^7+2^6*2^6*2^2+2^5*2^5*2^2*2^2...)=O(2^14*8)=O(2^17)이므로, 시간 제한 1초 내에 해결할 수 있다. 재귀함수에 시작점과 현재 색종이의 변의 길이를 전달한다. 칸의 색이 하나라도 다르면 잘라야 하기 때문에 비교 대상은 시작점의 색으로 하였다.  현재 색종이의 모든 칸을 확인하면서 다른 색을 가진 칸이 있다면, 4등분한 색종이를 나타내는 재귀함수를 실행한다. 현재 색종이의 모든 칸을 확인하면서 다른 색을 가진 칸이 없다면, 시작점의 색과 모두 같다는 의미이므..

🥅 문제https://www.acmicpc.net/problem/2606 🔍 설계1번과 연결된 컴퓨터들이 감염된다는 것에서 BFS를 활용해야 한다는 것을 알 수 있다. 방문 처리를 하여 중복해서 큐에 담지 않도록 설계하였다. 👊 풀이#include #include #include #include #include using namespace std; int n, m, a, b, result=0;vector> adj_list(101);vector visited(101);queue q;void bfs(){ visited[1] = true; q.push(1); while (!q.empty()){ int x = q.front(); q.pop(); for (int i=0; i> n >> m; for (i..

🥅 문제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..