swanzzz 님의 블로그

[오늘의 문제]https://www.acmicpc.net/problem/15684[오늘의 학습 키워드]구현시뮬레이션1. 문제설명H x N 크기의 사다리가 있습니다.이 사다리에는 사다리 발판이 총 M개가 주어집니다. 각각의 번호를 사다리 타기 게임을 통해 아래로 내려가는데 자기자신과 동일한 번호로 도착해야 합니다. 즉 1번은 1번에, 2번은 2번에,... N번은 N번에 도착해야 합니다.그러나 사다리의 발판이 존재하더라도 각각의 번호에 제대로 도착하지 못할 수 있죠 따라서 최대 3개의 사다리 발판을 추가해서 자기자신의 번호에 내려갈 수 있도록 만들어야 합니다. 만약 3개 이상 발판을 사용해야 하는 경우 의미가 없다고 판단해서 -1을 반환합니다. 몇개의 발판을 추가해야 자기자신의 번호로 내려가는 사다리를 만들..

[오늘의 문제]https://www.acmicpc.net/problem/20055[오늘의 학습 키워드]구현자료구조시뮬레이션1. 문제설명 컨베이어 벨트가 순서대로 동작합니다. 벨트에 로봇이 올라가면 내구도가 1 감소하고, 로봇이 다음번 벨트로 이동할때에도 내구도가 1 감소합니다. 벨트에 로봇을 올리고, 로봇이 이동하고, 벨트가 회전할때 모든 동작이 완료된 후 내구도가 K개 이상인 벨트가 있는 경우 종료하고 그때의 단계를 출력하는 문제 입니다.[제한사항]시간 제한 1초메모리 제한 512MB2 ≤ N ≤ 1001 ≤ K ≤ 2N1 ≤ Ai ≤ 1,0002. 접근방식문제의 요구사항을 그대로 구현만 하면 되는 쉬운 문제 입니다. 요구사항을 분석하면 컨베이어 벨트에 로봇을 올리는 위치는 항상 0번 이고 로봇이 내려..

[오늘의 문제]https://www.acmicpc.net/problem/17144[오늘의 학습 키워드]구현BFS1. 문제설명 문제를 요약하자면 미세먼지가 가득한 방에 공기청정기를 가동시켜 미세먼지를 최대 T초간 제거 후 방에 남아있는 미세먼지의 총 양을 출력하는 문제입니다. 미세먼지는 1초동안 동시에 확산을 시작하는데확산의 조건은 다음과 같습니다.미세먼지는 인접한 4방향으로 확산한다.인접한 방향에 공기청정기가 있거나, 벽이 있다면 확신이 일어나지 않는다.확산되는 양은 현재 위치 (i, j) // 5 의 양 만큼 확산된다.확산 후 현재 위치 (i, j) 에 남는 양은 확산된 미세먼지의 수 (i, j) // 5 x (확산된 미세먼지 수) 만큼 감소된다즉 i, j 는 (i, j) - (i, j) // 5 * ..

[오늘의 문제]https://www.acmicpc.net/problem/14890[오늘의 학습 키워드]구현자료 구조1. 문제설명 문제를 요약하자면 다음과 같습니다. 2N 개의 길이 존재할 때 지나갈 수 있는 길의 개수를 구하려고 합니다.지나갈 수 있는 길의 조건은 다음과 같습니다.길에 속한 모든 칸의 높이가 같아야 한다.또는 경사로를 설치해서 지나갈 수 있는 길을 만들어야 한다.경사로는 높이가 항상 1이며, 길이는 L 이다. 또 경사로의 개수는 매우 많아 모든 칸에 경사로를 놓을 수 있다.경사로는 낮은 칸과 높은 칸을 연결하며 다음과 같은 조건을 따른다.경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.경사로를 놓을 낮은 칸..

[오늘의 문제]https://www.acmicpc.net/problem/14500[오늘의 학습 키워드] DFS구현브루트포스 알고리즘1. 문제설명 보드의 크기 N, M이 주어질 때 해당 보드에 테트로미노 블록 1개만 놓아서 최대의 크기를 가지는 경우를 구하는 문제 입니다. 테트로미노는 위 그림처럼 5개의 모양이 존재합니다. 각 모양을 적절히 회전하거나, 뒤집어서 최대의 크기를 가지는 경우 1가지를 구해 그 크기를 출력하는 문제 입니다.[제한사항]시간 제한 2초메모리 제한 512MB4 ≤ N, M ≤ 500둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수..

[오늘의 문제]https://www.acmicpc.net/problem/3190[오늘의 학습 키워드]구현큐시뮬레이션자료구조1. 문제설명 흔히 생각하는 뱀게임 문제 입니다. 0, 0 좌표에서 시작해서 최초 오른쪽으로 이동을 실시합니다.뱀이 사과를 먹게되면 몸통의 길이가 늘어나고, 사과를 먹지 않은 경우 몸통의 길이가 늘어나지 않습니다. 이동중 뱀이 벽 혹은 자신의 몸통과 부딪힌다면 그 즉시 게임이 종료됩니다. 게임은 N x N 크기의 보드에서 진행하며 총 K개의 사과가 주어집니다. 그 다음 L번의 방향전환 횟수가 주어집니다. 이때 방향전환은 (시간, 방향) 순서로 주어집니다.즉, 게임진행 시간이 입력받은 방향전환의 시간과 동일할 때, 해당 방향으로 뱀에 회전한다는 소리 입니다. 이렇게 게임을 진행할 때 게..

[오늘의 문제]https://www.acmicpc.net/problem/3197[오늘의 학습 키워드]너비 우선 탐색구현1. 문제설명 두 마리의 백조가 호수에 살아갈 때 두 마리의 백조가 서로 만나려고 합니다. 그러나 호수를 덮고 있는 얼음이 두 백조가 만나는 것을 방해합니다. 호수가 차례로 녹을 때, 매일 물 공간과 접촉한 모든 빙판이 녹습니다. 며칠이 지나야 백조가 만날 수 있는지 계산하는 프로그램을 작성하시오[제한사항]시간 제한 1초메모리 제한 256MB1 ≤ R, C ≤ 1500 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. 2. 접근방식문제만 보면 구현 방식 자체는 간단합니다. 백조의 위치를 구한 뒤 시..

[오늘의 문제]https://www.acmicpc.net/problem/9328[오늘의 학습 키워드]BFS, 너비 우선 탐색그래프 이론, 그래프 탐색, 격자 그래프구현1. 문제설명 상근이가 빌딩을 탈출할 때 최대한 많은 비밀 문서를 가져오려고 합니다. 상근이는 빌딩의 외부에서 벽이 아닌 곳으로 출입하는데 이때 벽이 아니라는 의미는 빈 공간 혹은 문, 키 등을 의미합니다. 상근이는 문(대문자 영어)을 만났을 때 키(소문자 영어)가 있는 경우 해당 문을 열고 다음 위치로 이동합니다. 기존에 보유중인 키도 있고 빌딩에 흩어진 키를 주워서 문을 열어 이동할 수 도 있습니다. 상근이는 4방향으로만 이동이 가능할 때 최대한 많은 문서를 주울수 있는 경우를 찾아 출력하는 프로그램을 만들어야 합니다.[제한사항]시간 제..

[오늘의 문제]https://www.acmicpc.net/problem/11967[오늘의 학습 키워드]그래프 이론그래프 탐색너비 우선 탐색, BFS구현1. 문제설명 암소 배시는 불이 켜진곳 으로만 이동이 가능합니다. 1, 1 위치에 다른 방의 불을 켜고 끌 수 있는 스위치가 있을 때 해당 방의 불을 켠 후 불이 켜진방으로 이동이 가능합니다. 이렇게 해서 배시가 이동이 가능한 방의 개수를 구하는 문제 입니다.[제한사항]시간 제한 2초메모리 제한 512MB2 ≤ N ≤ 1001 ≤ M ≤ 20,0002. 접근방식 배시가 이동 가능한 좌표의 크기는 N x N 이고 불이 켜진 정보가 M개의 줄에 걸쳐 주어집니다. 이때 불의 정보는 x1, y1 -> x2, y2의 불을 켤 수 있습니다. 이 구조는 딕셔너리의 구조..

[오늘의 문제]https://www.acmicpc.net/problem/16920[오늘의 학습 키워드]그래프 탐색그래프 이론너비 우선 탐색, BFS구현1. 문제설명 격자판 위에 플레이어의 번호와 동일한 성이 존재합니다. 각 플레이어 별로 움직일 수 있는 범위 S가 주어질 때, 1번 플레이어 부터 9번 플레이어 까지 순서대로 자신의 성을 확장합니다. 예를들어 1번 플레이어는 성이 0, 0 위치에 존재하고 2칸의 범위를 움직일 수 있습니다.2번 플레이어는 3, 3에 성이 존재하고 1칸의 범위를 움직일 수 있습니다. 1턴 움직이면 각 플레이어의 성이 이렇게 확장 됩니다. 다음턴에는 이렇게 확장되어 1번 플레이어가 총 13칸을 차지하고 2번 플레이어는 3칸을 차지하게 됩니다. 이렇게 동작하도록 코드를 작성..