https://www.acmicpc.net/problem/20549 20549번: 인덕이의 고민 오리를 좋아하는 인덕이는 오리를 바라보며 마음의 안식을 얻는다. 오리는 N×N의 정사각형 모양으로 이루어진 인경호에서 유유자적하게 헤엄을 친다. 인경호는 1×1 크기의 칸으로 나누어져 있 www.acmicpc.net 사실 비트마스킹문제를 풀고 싶어서 태그를 보고 문제를 풀었는데 비트마스킹을 몰라도 풀 수 있는 문제였습니다. 필요한 배경지식 다익스트라 문제 해결 방법 NxN 격자에서 오리가 이동할 수 있는 방법은 3가지가 있습니다. 체스룰에서 나이트, 비숍, 룩의 이동과 같은 이동방법인데 각각의 이동방법에 가중치가 존재합니다. 이것을 '오리가 받는 과부하의 양' 이라고 하여 각각 A,B,C로 입력을 받는데, 이..
www.acmicpc.net/problem/9997 9997번: 폰트 첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다. www.acmicpc.net 필요한 배경지식 비트마스킹, 조합론에 대한 지식이 필요합니다. 문제 해결 방법 문제에서 구해야 할 테스트문장은 N개의 단어를 조합하여 만들 수 있으며 소문자'a'부터 'z'까지 26개가 문장에 모두 포함되어 있어야 합니다. 어떻게 N개의 단어를 조합하여 테스트 문장을 만들 수 있을지 생각해 보기전에, 문장안에 a~z까지의 문자가 존재하는지 확인할 방법을 먼저 생각해 봅시다. 확인할 개수가 26개밖에 되지 않기 때문에 가장..
백준 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] 의 최소값을 구하면..