두 수 XOR 합과 유사한 문제이다. 숫자를 이진수로 변경하여 트라이에 넣어주고, 숫자 중 i번째까지 XOR한 값을 prefix에 저장해서 답을 구한다. 같은 수를 XOR 연산하면 항상 0이 된다. 따라서 S[i] = A[1] ~ A[i]를 XOR 연산한 결과라고 한다면, A[i] ~ A[j]까지 XOR 연산한 결과를 S[j] - S[i - 1] 이라고 할 수 있다. 따라서 수를 트라이에 넣으면서 연산을 누적해나가며 S[i]와 S[j]를 XOR한 값이 가장 큰 것으로 찾는 것으로 변형할 수 있다. #include #include using namespace std; struct Node { int children[2]; bool valid; Node() { children[0] = children[1] ..
👻 문제 설명 BFS문제이지만, 인접한 칸으로 이동하는 기존 문제와 다르게 90도로 이동해야 하는 점 + 거울을 설치할 수 있는 곳까지 연속으로 쭉 이동해야하는 점이 달랐습니다. 이 점을 유의해서 BFS 코드를 조금 고쳐서 풀어보았습니다 : ) 😔 해결 과정 편의 상, 시작점 (#)에서 도착점(#) 까지 '빛이 이동한다'라고 표현하겠습니다. BFS를 수행하는 목적은, 빛이 시작점에서 도착점까지 이동하였을 때 '거울이 최소 몇 번 사용되느냐' 입니다. 이 말은 즉, '빛이 최소 몇 번 꺾이느냐'를 의미합니다. 따라서 거울을 놓을 수 있는 모든 위치에 대해서, 빛이 꺾일 수 있는 다음 위치를 모두 찾아 이동하는 것을 시뮬레이션하고 도착점(#)에 도달하였을 때 사용한 거울의 최솟값을 구하면 됩니다. 이 때 유..
🥲 문제 설명 https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net 🐹 문제 해설 이 문제는 아래 두 가지로 나뉜다. (1) 돌을 2개 놓는 부분 (경우의 수 : 400 * 400 = 160,000) (2) 죽일 수 있는 상대 돌의 개수를 구하는 부분 (경우의 수 : (400 * 400) ^ 3 = 64000000) 방문하지 않은 돌을 찾는다. 그 돌에 속한 그룹을 찾는다. 그룹은 최대 3개씩 속하므로, 4..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 설명 구현 태그에 속한 문제이다. 문제를 요약해보자. 매일 각 나라의 인구를 인접한 나라와 비교하면서, L 이상 R 이하의 인구 수의 차이를 가진 나라와 국경선을 모두 열어 연합을 만든다. 이 연합에 속한 나라들의 인구수의 평균만큼 각 나라의 인구를 세팅한다. 1, 2번 과정을 반복하다가 더 이상 국경선을 열 수 있는 나라가 없을 때 인구 이동을 종료한다. 코드 설명 구현 문제..
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제 설명 주사위를 굴릴 때마다 주사위의 숫자와 지도의 숫자가 계속해서 바뀌는 문제이다. 단순 구현 문제이므로 조건에 맞추어 주사위를 굴리는 상황을 구한다. 코드 설명 문제 해결 과정은 크게 세 가지로 나뉜다. K개의 방향으로 이동하는 것을 구현한다. 만약, 주사위가 이동할 수 없다면 이 명령을 무시한다. 입력된 방향으로 주사위를 ..
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 해설 단순 구현 문제이고, 처리해야하는 예외가 많아 시뮬레이션 해보고 구현해야하는 문제였다. 주의해야할 문제의 조건은 아래와 같다. 뱀의 머리가 먼저 이동한 후, 그 위치의 사과의 유무에 따라 꼬리의 이동 유무가 결정된다. 이 순서에 맞게 구현해야 한다. 방향을 전환할 때, 현재 뱀의 머리의 방향을 기준으로 왼쪽, 오른쪽 방향으로 전환한다. 뱀의 꼬리는 뱀의 머리가 지나간 위치로만 이동할 수 있다...
https://www.acmicpc.net/problem/28082 28082번: 기계오리 연구 인하대학교 기계공학과의 기계오리 연구실에서는 2023년 버전 기계오리를 완성하기 위해 실험을 진행하고 있다. 실험 도중, 기계오리에 1개 이상 $K$개 이하의 배터리를 삽입하면 기계오리가 언 www.acmicpc.net KnapSack을 응용한 DP 문제이다. 사용할 수 있는 배터리의 총 개수는 N, 기계오리에 장착할 수 있는 배터리의 최대 개수는 K이다. 배터리의 개수가 1 이상, K 이하일 때 만들 수 있는 모든 전력량을 출력하자. 배터리의 사용 개수가 K 이하인 전력량의 합이 하나라도 있다면 그 전력량은 출력한다. 따라서, 각 전력량의 합을 만들 수 있는 배터리의 최소 개수를 저장한 뒤, 최소 개수가 K..
https://www.acmicpc.net/problem/28081 28081번: 직사각형 피자 첫 번째 줄에 피자의 가로 길이 $W$와 세로 길이 $H$, 부원들이 먹을 수 있는 피자 조각의 최대 크기 $K$가 공백으로 구분되어 주어진다. 두 번째 줄에 가로 방향 커팅의 개수 $N$이 주어진다. 세 번 www.acmicpc.net 입력 제한이 큰 문제이기 때문에, 일반적인 브루트 포스 알고리즘으로 풀면 안 되고, 이분탐색 알고리즘으로 푼다. 가로 방향과 세로 방향에서의 피자 조각의 크기를 모두 배열에 저장한 다음, 각각의 가로 방향의 길이에 대해서 곱이 K 이하가 되는 세로 방향의 크기의 Upper bound 를 구한다. 이때 세로 방향에서의 피자 조각의 크기는 오름차순 정렬되어있으므로, Upper b..
https://www.acmicpc.net/problem/28079 28079번: 배 옮기기 치훈이는 배 \(N\)척을 강 건너편으로 옮기려고 한다. 강을 건너가거나 건너오기 위해서는 치훈이가 가지고 있는 배를 운전하여 건너야 한다. 배의 크기가 \(X\)라고 할 때, 치훈이가 그 배를 운전 www.acmicpc.net Bridge and torch problem과 유사한 문제로, 배가 한 번 이동하고 나면 다시 돌아와야 다음 과정을 진행할 수 있다는 점이 특징이다. 모든 배를 강 건너편 (오른쪽)으로 이동시키는 가장 최소 시간을 출력하자. 1. 문제의 상태를 비트마스크를 이용해 하나의 정점으로 만들어 그래프를 생성한다. 배의 크기 순대로 정렬 후, 강을 건너지 않은 배들은 0, 강을 건넌 배들은 1로 ..
