문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 방법 [i, j) 부분 구간의 합이 M으로 나누어 떨어지는 i, j 쌍의 개수를 구하는 문제이다. 배열의 크기 N과 나누는 수 M이 큰 숫자이기 때문에 모든 경우를 계산해보는 방법은 불가능하다. 때문에 배열을 입력 받을 때 부분 합을 미리 계산해놓는다. PrefixSum[j] - PrefixSum[i] % M = 0이 만족하면 Prefix..
프로그래밍
포인터를 사용하는 이유 포인터가 왜 필요할까? 포인터를 왜 쓸까? 포인터를 왜 사용할까? 에 대해서 생각해보기 전에... 포인터에 대해서 잘 모른다면 아래 '포인터란 무엇인가'부터 읽어보자. 이미 배경지식이 있다면 상관없다. 화씨를 섭씨로 바꾸는 프로그램을 작성한다고 가정해보자. #include // 화씨 온도를 입력받아 섭씨단위로 바꿔준다. void ToCelsius(double F) { F = (F - 32)/1.8; } // 물론 이렇게 반환한 값을 호출부에서 활용해도 된다. // 하지만 본 글에서는 위의 구현에 대해서 다룬다. double ToCelsius2(double F) { return (F-32)/1.8; } int main() { double temperature = 32; // 화씨 3..
문제 https://www.acmicpc.net/problem/2001 2001번: 보석 줍기 첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 www.acmicpc.net 풀이 방법 1194번 달이 차오른다, 가자와 비슷한 문제이다. 이 문제에서는 열쇠를 갖고 이동하는 것이 아니라 보석을 줍고 이동하며, 시작점으로 돌아왔을때 보석의 최대 개수를 출력해야한다. 1194번과 유사하게 보석이 최대 14개이므로 보유한 보석을 최대16,384 (1
문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 방법 2206번 벽 부수고 이동하기와 비슷한 문제이다. 이 문제에서는 벽을 부수는 것이 아니라 열쇠로 이동하면 열쇠를 획득하여 해당하는 문을 열 수 있는 것이 특징이다. 따라서 큐에 좌표와 갖고 있는 키 상태를 넣어줘야 하며, 방문도 마찬가지로 키를 갖고있는 상태에서 방문한 좌표를 체크해줘야한다. (3차원 공간) 키를 갖고 있는 것을 어떻게 표현해야할지가 ..
