작심 24/7

11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에 www.acmicpc.net 그냥 cin cout 쓰면 무조건 시간 초과 난다. ios_base::sync_with_stdio(false); cin.tie(NULL); 를 적어주거나 scanf printf를 써야 한다. DP와 세그먼트 트리, 두 가지 방식으로 풀어 보았다. 1. DP i번째 칸에 1번째 수부터 i번째 수까지 더한 값을 저장해놓고 a부터 b까지의 합을 출력할 때는 b번째 값에서 a - 1번째 값을 빼서 출력한다. #incl..

19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 격자 벡터엔 칸마다 냄새를 남긴 상어의 번호, 남은 시간을 저장하고 상어 벡터엔 상어 번호, x 좌표, y 좌표, 방향을 저장한다. 상어 방향 3차원 배열은 [상어 번호][방향][순위]를 인덱스로 가지고 값은 그때의 방향이다. 1. 상어 벡터를 처음부터 끝까지 돌면서 상어 방향 배열을 이용해 현재 상어의 방향일 때의 우선순위에 맞게 이동할 수 있는 빈칸을 찾는다. →이동할 수 있는 빈칸이 있다면 임시 벡터에 상어 번호,..

17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net 클래스를 하나 만들어 int 형 : 말의 좌표 x, y, 방향 d와 string 형 : 말이 쌓아져 있는 상태 a 의 형태로 벡터에 입력받았다. 현재 말이 현재 칸에서 현재 방향으로 이동하려고 할 때 이동하려는 칸이 1. 파란색이거나 체스판을 벗어나는 경우 방향을 반대로 바꾼 뒤 그 방향으로 이동할 때 그 칸이 파란색이거나 체스판을 벗어나는 경우는 continue로 넘겨버리고 그 외의 경우는 2, 3번의 경우를 만족하는지 계속 비교하러 간다. 2. 하얀색인 ..

17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름�� www.acmicpc.net 경계의 길이 d1과 d2의 길이가 각각 1부터 N-1까지일 때 만들 수 있는 꼭짓점 A, B, C, D를 기준으로 나누어진 1, 2, 3, 4, 5 선거구의 인구수를 구해야 한다. 한 칸을 꼭짓점 A라 할 때, 이 점을 기준으로 나머지 꼭짓점 B, C, D도 만들어 최소 한 번이라도 다섯 선거구로 나눌 수 있는 조건을 만족시키는 칸은 파란색 경계선 안의 칸들이다. 빨간색으로 표시된 칸들은 B, C, D 세 점 모두를 만들 수 없는 경우 즉, 다이아몬드 모양의 경계선..

9202번: Boggle 문제 상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 상근이는 한 번도 부인을 Boggle�� www.acmicpc.net 단어 사전을 만들 때 트라이 알고리즘을 이용하여 트리를 만들면 트리 생성 시 O(L*M), 탐색 시 O(L) (L : 제일 긴 문자열의 길이, M : 총 문자열의 수) 로 빠르게 문자열을 탐색할 수 있다. Boggle 보드의 모든 칸마다 가로, 세로, 대각선으로 인접한 칸을 DFS로 글자 수 1부터 8까지 탐색한다. 탐색하면서 사전에 이 단어가 있는지 찾는데 해당 단어가 있다면 set에 있는 단어인지 체크해준 뒤 (중복 찾기 방지 위해) s..

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄�� www.acmicpc.net 일반적인 방법으로 구간의 합을 구하면 O(N)이지만 이 문제에서는 시간 초과가 걸릴 가능성이 아주 높기 때문에 O(logN)인 세그먼트 트리를 이용하여 구해야 한다. 일차원 배열을 이용하여 이진 트리를 만드는 데 계산을 편하게 하기 위해서 루트를 인덱스 1로 잡고 왼쪽 노드는 부모 노드 * 2, 오른쪽 노드는 부모 노드 * 2 + 1 의 형태로 지정한다. 루트 노드를 반으로 나누어 구간 A, 구간 B..

17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 재귀 호출로 상어를 이동시켰다가 시간 초과 걸려서 수학적 계산으로 풀었다. B 상어를 예로 들어 화살표 길이 = 현재 위치에서 끝까지 갈 때 걸리는 속력 이라 할 때 속력 ≤ 화살표 길이 일 때는 현재 방향 그대로 한 번에 이동이 가능하지만 속력(5) > 화살표 길이(3) 일 때는 방향을 바꿔 왔다 갔다 해야 하므로 왕복 횟수 : (속력 - 화살표 길이) / 총 길이 왕복 후 남은 속력 : (속력 - 화살표 길이) % 총 길이 를 구해준다. 이..

16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 쉽길래 대충 짜고 제출했다가 시간 초과로 여러 번 낭패 본 쉽지 않은 문제이다. sort로 정렬하기 전에 죽은 나무를 제외시키는 것이 관건인 것 같다. 이차원 벡터를 이용하여 나무들을 저장해주었다. 봄과 여름 각 칸에 있는 모든 나무들을 검사한다. 양분을 먹을 수 있는 나무는 살 수 있으므로 큐에 나이를 넣어주고 양분을 먹지 못하는 나무는 양분이 되므로 나이/2 값을 양분 변수에 넣어준다. 현재 칸의 모든 나무들의 검사가 끝나면 죽은 나무를 걸러주..