티끌모아 태산

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 설명 우선, 크기가 100 x 100 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1 x 1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램 작성. ( 0 (0, (0+1)) 2세대: 0 1 2 1 -> (0, 1, (1+1), (0+1)) 3세대: 0 1 2 1 2 3 2 1 -> (0, 1, 2, 1, (1+1), (2+1..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 설명 최종 구해야하는 것은 톱니바퀴의 초기 상태와 회전시키는 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오. 톱니바퀴를 총 K번 회전시킨다. 방향은 시계 방향과 반시계 방향이 있다. 톱니바퀴를 회전시키기 위해서는 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야한다. 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수 있고, 아닐 수 있다. 예를들어, 톱니바퀴 A를..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 설명 맵 위에 테트로미노 하나를 놓아서 놓인 칸에 쓰여 있는 수들의 합을 최대로 구하는 문제이다. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야하며, 회전이나 대칭을 시켜도 된다. 핵심 아이디어 DFS를 활용하기! 테트로미노를 살펴보면 5개중 4개는 DFS로 구현이 가능한데 한 개는 불가능하다. T자를 구현하기 위해서는 DFS를 돌 때, 현재 위치를 가리키는 커서를 움직이..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 설명 우선, 학생의 만족도의 총 합을 구하는 문제다. 학생의 만족도는 자리 배치가 모두 끝이 난 후에 구할 수 있다. 자리 배치가 모두 끝난 후, 해당 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야한다. 좋아하는 학생의 수가 0이면 해당 학생의 만족도가 0이고 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다. 상어 초등학교의 교실은 N x N 격자이다. 학교에 다니..

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 설명 우선 구하는 값은 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구하는 것이다. 문제의 조건을 잘 살펴보고 주어진 조건대로 구현하면 되는 문제이다. 물고기는 번호와 방향을 갖고 있다. 1

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 설명 토네이도를 시전하면 격자의 가운데 칸 부터 토네이도의 이동이 시작. 토네이도는 한 번에 한 칸 이동한다. 토네이도가 한 칸 이동할 때마다 모래는 일정한 비율로 흩날리게 된다. x에서 y로 이동하면, y의 모든 모래가 비율과 a가 적혀 있는 칸으로 이동한다. 비율이 적혀 있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 설명 기존에 있는 치킨집의 수를 줄여서 최대 M개로 유지한다. 그 상태에서 일반집들로부터 M개의 치킨 집까지의 거리를 줄이는 것이 목표이다. 이후에 도시의 치킨 거리 합의 최솟값을 계산하는 문제다. 핵심 아이디어 우선, 치킨집의 개수 범위는 M

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 설명 안전 영역 크기의 최댓값을 구하는 문제이다. 벽을 3개 설치하는 모든 경우의 수를 다 계산해야한다. 전체 맵의 크기가 8x8 이므로 (3 ≤ N, M ≤ 8) 벽을 설치할 수 있는 모든 조합의 수는 최악의 경우(바이러스가 하나도 존재하지 않을 경우) 64Combination3이 될 것이다. 이는 100,000보다 작은 수 이므로, 모든 경우의 수를 고려해도 제한 시간 안에 해결 가능. 핵심 아이디어 파이..

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 설명 이 문제 역시 이어진 격자문제이다. "격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다." 핵심 아이디어 문제에 주어진 요구조건을 그대로 따라하면 되는 시뮬레이션 문제 8가지 방향 고려 이어진 격자 고려 크기가 N x N 인 2차원 배열 만들기. 각 요소는 빈 리스트로 초기화 ..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 설명 이 문제는 주어진 조건을 잘 구현하면 되는 전형적인 시뮬레이션 문제이다. 청소하는 영역의 개수를 구하는 문제. 핵심 아이디어 전형적인 시뮬레이션 문제 북 동 남 서 방향 정의 하기 # 북 동 남 서 방향 정의, x를 행(위,아래) y(좌,우)를 열로 생각하기 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] 반시계 방향..