CODING(18)
-
백준 알고리즘 16234_인구이동 C
문제 (링크)16234번: 인구 이동 (acmicpc.net) 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 사고과정 먼저 생각해야할 것은 현재 각 나라의 인구 상태에서 연합이 만들어질 수 있는가이다. 이후 visit배열에 형성된 연합끼리 정보를 달리한 뒤 인구를 분배하면 된다고 생각했다. 그런데 코드를 짜다보니 굳이 연합이 가능하지 탐색하는 것과, 연합을 만든다음 인구를 분배하는 과정을 분리할 필요가 없다는 것을 깨달았다. 내코드 #include #include typedef struct { ..
2021.02.24 -
백준 알고리즘 15686_치킨배달 C
문제 (링크)15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 사고과정 문제에서 입력이 그래프를 활용할 수 있도록 주어져서 조금 흠칫했다. 하지만 문제에서 요구하는 것은 각 집에서 선택한 치킨집까지의 거리중 최소거리를 합한 것이므로, 각 좌표의 정보를 순차적으로 담기만 하면 된다. 이후 집의 좌표와 치킨집의 좌표를 따로 저장하고, 재귀함수를 통해 치킨집을 골라내면 된다. 내코드 #include #define HOUSE 1 #define CHI..
2021.02.23 -
백준 알고리즘 15685_드래곤커브 C,C++
문제 (링크)15685번: 드래곤 커브 (acmicpc.net) 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 사고과정 처음에 문제가 조금 헷갈려서 아래에 있는 예시까지 보고 확실하게 이해했다. 먼저 생각한 것은 주어지는 각 드래곤커브마다 정보를 업데이트 해야한다. 이후 격자 안의 점들을 탐색하며 사각형을 찾아야겠다고 생각했다. 그런데 문제는 어떻게 드래곤 커브를 주어진 세대만큼 업데이트 하느냐이다. 먼저 문제에서 주어진 격자는 우리가 흔히 사용하는 좌표평면을 x축 대칭한 모양이다...
2021.02.19 -
백준 알고리즘 15684_사다리 조작 c
문제 (링크)15684번: 사다리 조작 (acmicpc.net) 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 사고과정 문제를 처음 읽었을 때 왜이렇게 정답률이 낮은거지?라고 생각할 만큼 그리 어려운 문제는 아니라고 생각했다. 그러나 시간제한이 2초라고 되어있기 때문에 우리는 시간초과를 유의하여 코드를 짜야한다. 조건 입력 -> 사다리를 x번(0~3) 추가 -> 사다리를 탐색 -> 반복 --> 종료조건을 만족하면 사다리 최소 추가회수 출력 의 구조를 생각했다. 그러므로 함수는 총 2개 ①사다리 탐색함수와 ②..
2021.02.17 -
백준 알고리즘 15683_감시 c++
문제 (링크)15683번: 감시 (acmicpc.net) 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 사고과정 문제 자체는 그리 어렵진 않았지만 예기치 못한 오류 때문에 시간을 많이 썼다. 처음엔 완전탐색을 하고싶지 않아서 답을 도출하는 망법을 생각했다. cctv가 각 방향을 탐색할 때 최대한 많은 구역을 탐색하면서 다음 cctv로 넘어가는 것인데, 아니나 다를까 예외적인 상황이 생겨서 오답처리 되었다. 그래서 결국 재귀함수를 이용하여 전체를 탐색하기로했다. 내가 c++ vector를 사용하는 이..
2021.02.15 -
백준 알고리즘 14891_톱니바퀴 C
문제 (링크)14891번: 톱니바퀴 (acmicpc.net) 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 사고과정 톱니바퀴를 돌리는데 서로 마주보고 있는 톱니의 상태에 따라 같이 돌아가느냐와 돌아가지 않느냐가 문제이다. 처음엔 index를 줄이고 늘여가며 비교를 하려고 했다. a번 톱니의 2번 톱니는 시계방향으로 돌아가면 3번이 되기 때문에, 비교index를 1줄여주는 방식이다. 하지만 마지막에 결국 12시 방향의 톱니 상태를 알아야 하고, 위와 같은 방식으로 하려면 변수를 6개 지정해야 해서 헷갈릴 것..
2021.02.11