백준 20058번 - 마법사 상어와 파이어스톰
www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 기존의 상어 시리즈와 비슷한 시뮬레이션 문제였습니다. 파이어스톰 시전시 시뮬레이션 과정은 다음과 같습니다. 주어진 L값에 따라 얼음판을 시계방향으로 90도 회전한다. 얼음이 있는 칸마다 인접한 칸중에서 얼음이 있는 칸의 개수가 3개 이상이 아니면 해당칸의 얼음의 양이 1줄어든다. 1번과정을 구현하기 위해 회전하기전 얼음판과 회전후의 얼음판을 비교해보면 얼음판의 회전은 위의 그림에서 초록색 사..
백준 1516번 - 게임 개발
www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 다음은 위상정렬의 개념을 이해했다고 가정한 풀이설명입니다. 문제의 조건을 토대로 의 건물을 짓기위한 순서를 그래프로 표현하면 다음과 같습니다. 문제의 조건을 보면 모든 입력은 위의 그림처럼 방향성이 있는 비순환 그래프(DAG)로 나타낼 수 있고 건물을 짓기 위한 순서를 필요로 하므로 각각의 건물을 완성하기 위한 최소시간은 위상정렬을 이용해 구할 수 있습니다. 위상정렬로 순서를 구하는 과정에서 n번건물..
백준 20057번 - 마법사 상어와 토네이도
www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 토네이도가 한칸 이동할때마다 흩날리는 모래를 격자에 업데이트하면서 정해진 범위밖으로 나간 모래의 총량을 계산하는 문제입니다. 구현해야 할 내용은 크게 두가지로 나눠볼 수 있습니다. 토네이도 이동경로 인덱싱 이동 방향에 따른 모래비율 맵핑 우선 토네이도 이동경로 인덱싱은 토네이도 시작점(N/2, N/2)을 기준으로 위치가 바뀌는 방향의 순서가 ← , ↓ , → , ↑ 이고 방향이 ..
www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 아래의 주어진 과정을 그대로 코딩하면 되는 구현문제였습니다. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다. 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다. 파이어볼은 4개의 파이어볼로 나누어진다. 나..
www.acmicpc.net/problem/2031 2031번: 이 쿠키 달지 않아! 첫 번째 줄에 4개의 자연수 T, N, D, K가 주어집니다. (1 ≤ T ≤ 109, 1 ≤ N ≤ 106, 1 ≤ D ≤ 109, 1 ≤ K ≤ 10) 두 번째 줄에 N 종류의 음식 각각을 먹을 시각을 나타내는 N 개의 자연수 a1, ..., aN이 주어집 www.acmicpc.net 재미있는 DP문제였습니다. 다이어트 효과가 최대가 되려면 다이어트가 효과가 유지되는 시간안에 음식이 가장 많이 포함되어 있어야 합니다. 우선 단순하게 K=1일때의 문제를 생각해 봅시다. 위에서 정의한 문제를 'D만큼의 범위안에 포함할 수 있는 원소의 최대 개수'로 치환할 수 있습니다. 그렇다면 이 문제는 정렬과 이분탐색을 이용하면 O(..
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] 의 최소값을 구하면..
백준 21611번 - 마법사 상어와 블리자드
www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 백준 21610번 - 마법사 상어와 비바라기 백준 21608번 - 상어 초등학교 백준 21609번 - 상어 중학교 새로 올라온 삼성 4문제 중 구현 난이도가 가장 어려운 문제였습니다. M개의 쿼리마다 주어지는 방향(d)과 거리(s)를 이용하여 블리자드 마법 시전시 수행되는 과정은 다음과 같습니다. d방향, 거리가 s이하인 모든 칸의 구슬을 파괴하며 파괴된 칸은 빈 칸이 된다. 구슬이 파괴된 후..
www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 백준 21608번 - 상어 초등학교 문제와 비슷한 난이도의 단순 구현 문제였습니다. 시뮬레이션 과정1,2,3을 move 함수, 4를 copyWater 함수 그리고 과정5를 makeCloud함수에 담았습니다. c++ 전체 코드 #include #define xx first #define yy second using namespace std; typedef pair pii; int N,M; int m[51]..