https://www.acmicpc.net/problem/10564 10564번: 팔굽혀펴기 각각의 테스트 케이스에 대해서, 동혁이가 응원하는 팀이 득점한 점수의 최댓값을 출력한다. 만약, 불가능한 경우에는 -1을 출력한다. www.acmicpc.net 1년전쯤 한창 DP문제를 풀며 자신감에 차 있을때 풀다가 벽을 느끼며 포기했던 문제였다. 이제는 풀 수 있을것 같아서 도전해 봤는데, 쉽진 않지만 생각하는 대로 문제가 풀리니 뿌듯했다. 필요한 배경지식 다이나믹 프로그래밍 BFS 문제 해결 방법 배낭문제(Knapsack Problem) 풀듯이 문제를 해결했다. 득점의 종류를 이용하여 나올 수 있는 총 팔굽혀펴기의 수를 탐색하는 방법이다. bool dp[i][j] : 총 i점일때 j번 팔굽혀펴기가 가능한가 ..
https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 필요한 배경지식 다익스트라 or BFS DP 문제 해결 방법 이모티콘 N개를 만들기 위한 시간의 최소값을 출력하기 위해 다음과 같은 DP배열을 사용했습니다. dp[N][C] = 현재 이모티콘이 N개이고 클립보드에 저장된 이모티콘의 개수가 C개 일때, 필요한 시간의 최솟값 이렇게 정의하면 3가지 연산에 대하여 다음과 같은 식이 성립합니다. 현재 이모티콘의 개수가 n, 클립보드에 복사된 이모티콘의 개수..
https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 필요한 배경지식 1번 풀이 : DFS, BFS 2번 풀이 : BFS, 외판원 문제(TSP) 3번 풀이 : BFS, DP, 비트마스킹 문제 해결 방법 방의 크기가 최대 20*20이므로 최단경로를 구하기 위해 BFS를 한번 수행하는 시간은 크게 문제가 되지 않습니다. 더러운 칸의 개수가 10개이므로 BFS를 최대 11번 수행하여 모든 더러운 칸과 로봇청소기 사이의 거리를 어렵지 않게 구할 수 있습니다. (di..
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 필요한 배경지식 DFS, BFS 문제 해결 방법 모든 빈칸에 바이러스가 있게 되는 최소 시간을 구해야 합니다. DFS를 이용하여 활성화할 M개의 바이러스를 고르고, 해당 바이러스들을 시작노드로 BFS를 수행하여 최소 시간을 구해낼 수 있습니다. 바이러스가 총 k개 있고 m개의 바이러스를 활성화 시킬 수 있다면 C(k,m) 만큼 BFS를 수행하여 최소 시간을 구해야 합니다. 최소시간을 구하는 과정에서 바이러..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 방법 BFS를 이용한 시뮬레이션 구현문제입니다. 모든 인접한 나라와 나라사이에 국경선이 열려있는지, 즉 인접한 나라로 이동할 수 있는지 확인한 다음, 만약 이동할 수 있다면 그 나라를 시작점으로 하여 BFS를 수행하고 인구이동 결과를 업데이트 합니다. 이때 방문처리도 같이 해주어야 합니다. 노드마다 이동할 수 있는지 확인하는 코드가 chkAlly 함수에 구현되어 있고 시작..
https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 문제 해결 방법 단순한 너비 우선 탐색(BFS) 문제입니다. 오른쪽과 아래로만 이동할 수 있다는 것과 한 번에 이동할 수 있는 칸의 수는 현재 밟고 있는 칸에 쓰여 있는 수라는 것만 잘 처리해 주면 주면 됩니다. C++ 전체 코드 #include #define xx first #define yy second using namespace std; using pii = pair; int N; int m[..
www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 기존의 상어 시리즈와 비슷한 시뮬레이션 문제였습니다. 파이어스톰 시전시 시뮬레이션 과정은 다음과 같습니다. 주어진 L값에 따라 얼음판을 시계방향으로 90도 회전한다. 얼음이 있는 칸마다 인접한 칸중에서 얼음이 있는 칸의 개수가 3개 이상이 아니면 해당칸의 얼음의 양이 1줄어든다. 1번과정을 구현하기 위해 회전하기전 얼음판과 회전후의 얼음판을 비교해보면 얼음판의 회전은 위의 그림에서 초록색 사..
www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 최단경로를 찾는 문제입니다. 벽을 1회만 통과할 수 있는데 이러한 경우 방문처리 배열크기를 늘리지 않고 풀 수 있는 방법이 있습니다. 시작점에서부터 도착점까지 BFS를 수행하여 얻은 최단거리 정보 bfs와 (코드에서 bfs배열) 도착점에서부터 시작점까지 BFS를 수행하여 얻은 최단거리 정보 rbfs를 구한 후 특정 위치(i,j) 에서 bfs[i][j] + rbfs[i][j] 의 최소값을 구하면..