https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제를 제대로 읽지않아 한참동안 헤매었던 문제였습니다. 턴이 진행되던 중에 말이 4개 이상 쌓이면 게임을 끝내야 하는데 K개와 비교한 것이 문제였습니다. 필요한 배경지식 std::vector 컨테이너에 대한 이해 문제 해결 방법 Vector를 잘 활용하면 직관적으로 풀어낼 수 있습니다. 선언한 변수의 정보는 다음과 같습니다. using pii = pair; using dpi = pair; int ..
https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 입력으로 주어지는 물건의 대소관계를 그래프로 표현하면 사이클이 없는 방향 그래프(DAG)로 표현할 수 있고 결과를 출력하기 위해 두 물건을 비교해야 하므로 위상정렬이 먼저 떠올랐습니다. 하지만 모든 물건들간에 비교가 필요하고 N의 최대가 100이라는 점에서 플로이드 와샬 알고리즘을 해결방법으로 생각해 낼 수 있었습니다. 필요한 배경지식 플로이드 와샬 알고리즘 : Floyd..
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 필요한 배경지식 이분탐색, 매개 변수 탐색 : parametric search 문제 해결 방법 답으로 출력될 값(배정될 예산)을 기준으로 하여, 매개 변수 탐색을 하면 됩니다. 즉, 이분탐색으로 배정될 예산을 구하는 과정에서 그 예산이 배정될 수 있으면 예산을 늘리고 배정될 수 없다면 줄이면서 가장 큰 값을 찾아나가는 방법입니다. 이분탐색의 구현은 lower bound 방식을 활용하여 구현했..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 방법 BFS를 이용한 시뮬레이션 구현문제입니다. 모든 인접한 나라와 나라사이에 국경선이 열려있는지, 즉 인접한 나라로 이동할 수 있는지 확인한 다음, 만약 이동할 수 있다면 그 나라를 시작점으로 하여 BFS를 수행하고 인구이동 결과를 업데이트 합니다. 이때 방문처리도 같이 해주어야 합니다. 노드마다 이동할 수 있는지 확인하는 코드가 chkAlly 함수에 구현되어 있고 시작..
백준 14891번 - 톱니바퀴
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제 해결 방법 나머지 연산을 잘 이용하면 문제를 쉽게 해결할 수 있습니다. 아래의 그림은 톱니바퀴의 시계방향 회전과 그 상태정보를 0~7인덱스로 나타낸 그림입니다. 위 그림과 같이 톱니바퀴의 상태정보를 0~7로 인덱싱하고 12시방향의 상태정보 인덱스를 now라고 한다면,비교해야 할 위치는 다음과 같습니다. 오른쪽과 맞닿은 톱니바퀴 인덱스 = (now+2)%8 왼쪽과 맞닿은 톱니바퀴 인덱스 ..
https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 문제 해결 방법 단순한 너비 우선 탐색(BFS) 문제입니다. 오른쪽과 아래로만 이동할 수 있다는 것과 한 번에 이동할 수 있는 칸의 수는 현재 밟고 있는 칸에 쓰여 있는 수라는 것만 잘 처리해 주면 주면 됩니다. C++ 전체 코드 #include #define xx first #define yy second using namespace std; using pii = pair; int N; int m[..
백준 15806번 - 영우의 기숙사 청소
https://www.acmicpc.net/problem/15806 15806번: 영우의 기숙사 청소 통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검 www.acmicpc.net 큐와 간단한 규칙을 이용한 구현문제였습니다. 문제 해결 방법 곰팡이는 1일이 지나면 위와 같이 8개로 증식합니다. 단순한 풀이 방법으로 1일마다 곰팡이 하나하나 8개로 나누어 저장하는 방법을 생각해 봅시다. N이 최대 300이고 t가 최대 10000이므로 최악의 경우 초기 곰팡이가 90000개이고 10000일 후의 결과를 알아야 할때 대충 (90000 * 8 * 10000) 만큼의 수행시간이..
https://www.acmicpc.net/problem/20549 20549번: 인덕이의 고민 오리를 좋아하는 인덕이는 오리를 바라보며 마음의 안식을 얻는다. 오리는 N×N의 정사각형 모양으로 이루어진 인경호에서 유유자적하게 헤엄을 친다. 인경호는 1×1 크기의 칸으로 나누어져 있 www.acmicpc.net 사실 비트마스킹문제를 풀고 싶어서 태그를 보고 문제를 풀었는데 비트마스킹을 몰라도 풀 수 있는 문제였습니다. 필요한 배경지식 다익스트라 문제 해결 방법 NxN 격자에서 오리가 이동할 수 있는 방법은 3가지가 있습니다. 체스룰에서 나이트, 비숍, 룩의 이동과 같은 이동방법인데 각각의 이동방법에 가중치가 존재합니다. 이것을 '오리가 받는 과부하의 양' 이라고 하여 각각 A,B,C로 입력을 받는데, 이..