CodeDrive

문제:

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력:

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력:

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

풀이방법:

 한 정점에서 다른 정점으로 가는 최소 비용을 구하는 알고리즘에는 다익스트라 알고리즘이 있다. 따라서 해당 문제를 다익스트라 알고리즘을 사용해서 풀었다.

 해당 문제에서 조심해야 하는 점은 출발 도시와 도착 도시가 한 쌍으로 주어지지 않는다는 것이다. 즉 A 도시에서 C 도시로 이동하는 버스가 여러번 입력으로 들어올 수 있다. 그러므로 입력을 받을 당시에 도시간에 이동하는 비용은 항상 최소가 되도록 유지시켜 준다.

 다익스트라 알고리즘은 heapq를 사용한 방법을 사용하여 구현을 했다.

문제링크:

https://www.acmicpc.net/problem/1916

케빈 머피의 Machine Learning 책을 보고 정리한 내용들입니다.

1.1 Machine Learning: what and why?

현재 우리는 빅데이터 시대에 살고 있으며, 수많은 양의 정보들을 마주하고 있다. 이러한 데이터들을 분석하기 위해 자동화된 데이터 분석 기법이 필요하게 되었고, 머신 러닝이 이러한 역할을 수행할 수 있다. 머신 러닝은 데이터의 패턴을 자동으로 인지하고, 다뤄지지 않은 패턴을 사용해 미래의 데이터를 예상하거나 불확실성 아래서 여러 종류의 결정을 선택하는 방법이다.

1.1.1 Types of machine learning

머신 러닝은 보통 두 개의 타입으로 구분할 수 있다.

1. Predictive, supervised learning
   • 레이블이 있는 입출력의 쌍이 주어졌을 때, 입력 x로 출력 y를 매핑하는 함수를 학습하는 것이 목표
   • 입력 x는 D차원 벡터로서 특징(feature), 속성(attribute), 공변량(covariance)라고 한다.
   • 출력 y는 한정된 값을 가지는 범주형 변수, 실수 값을 가지는 스칼라 변수가 있을 수 있다.
     • y가 범주형인 경우 분류(classification), 실수인 경우는 회귀(regression)이라고 한다.
2. Descriptive, unsupervised learning
   • 해당 방법에서는 입력만이 주어지고, 데이터 내의 흥미있는 패턴(interesting pattern)을 찾는 것이다.
   • 찾고자 하는 패턴이 주어지지 않기 때문에, 정의가 불분명하고, 에러를 측정할 수 있는 명확한 방법이 없다.
3. Reinforcement learning
   • 보상(reward)이 주어질 때 동작이나 행동을 배울 때 유용하다.
   • RL에 대해서는 이 책에서 자세히 다루지 않도록 한다.

1.2 Supervised learning

1.2.1 Classification

Classification의 목적은 입력 x로부터 출력 y를 매핑하는 것을 학습하는 것으로, y는 1~C의 값을 가지며, C는 class의 갯수를 의미한다. C=2인 경우에는 binary classification이라 하고, C > 2는 multiclass classification이라고 한다.
훈련 데이터에 대해서 학습을 하고 예측을 하는 것을 쉽기 때문에 classification의 주요 목적은 전에 보지 못했던 데이터들에 대해서도 답을 정확하게 예측하는 것(Generalization)이다.

1.2.1.2 The need for probabilistic predictions
주어진 입력 벡터 x와 훈련 집합 D에 대해 가능한 레이블들의 확률 분포를 나타낸다. 일반적으로 이 것은 길이가 C로 나타난다. 훈련 집합 D 뿐만 아니라 테스트 입력 x에 대한 조건부 확률이라는 것을 명시적으로 나타내기 위해 표기법에서 조건식 기호 | 의 오른쪽에 D와 x를 둔다.

확률적인 결과가 주어진다면, 다음의 식을 사용하여 레이블 값이 참인 경우에 대해 최선의 추측을 계산할 수 있다.

1. 문서 분류와 이메일 스팸 필터링
2. 꽃 분류
3. 이미지 분류와 글씨 인식
4. 얼굴 검출과 인식

1.2.2 Regression

Regression은 결과 변수가 연속적이라는 것을 제외하고 분류와 같다. 다음 그림은 단순한 예시를 보여준다.

• 현재 시장 상황과 다른 가능한 정보를 통해 다음 날의 주식 시장을 예측하는 것
• YouTube를 보는 사용자의 나이 예측
• 날씨 데이터와 시간, 문의 센서를 통해 건물 안의 온도를 예측하는 것

1.3 Unsupervised learning

Supervised learning과는 다르게 각 입력에 대해 기대되는 출력이 주어지지 않는다. 대신 작업을 확률 밀도 추정의 하나로 공식화한다. 즉, p(x|theta) 형태의 모형을 설계하는 것이 목표다. 이 말은 Unsupervised learning은 비조건적인 밀도 추정 문제에 해당한다.

1.3.1 Discovering clusters

Unsupervised learning의 기본이 되는 예제로 데이터를 그룹으로 clustering하는 문제다. 아래 그림은 210명의 키와 몸무게 대한 데이터들이다. 여러 개의 클러스터나 하위 그룹이 있는 것으로 보인다. K가 클러스터의 숫자를 의미한다고 하면, 첫 번째 목표는 p(K|D)를 예측하는 것이다. Supervised learning에서는 남자/여자와 같은 클래스가 있지만 Unsupervised learning은 클러스터의 갯수를 자유롭게 설정할 수 있다.
두 번째 목표는 각 데이터가 어떤 클러스터에 속하는지를 추정하는 것이다.(b)는 K=2일 때의 결과에 해당한다.

이 책에서는 model based clustering에 초점을 맞춘다. 모형 기반 클러스터링은 객관적인 방법으로 여러 모형을 비교할 수 있고, 여러 모형을 더 큰 시스템으로 조합할 수 있다.

클러스터링의 실제 응용은 다음과 같다.

• 천문학에서 천제 물리학의 측정값을 클러스터링하여 새로운 타입의 별을 발견할 수 있다.
• e-커머스에서 구입 내역과 웹 서핑을 분석하여 사용자들을 분석할 수 있고, 각 그룹에 타켓팅한 광고를 설정할 수 있다.

1.3.2 Discovering latent factors

고차원의 데이터를 처리할 때에는 데이터의 'essence'을 가지고 있는 작은 차원의 부분 공간으로 사영시키는 것이 유용하다.이것을 차원 축소라고 부른다. 아래 그림은 간단한 예시로, 3차원의 데이터를 2차원 평면으로 투영한 것이다.

1.3.3 Discovering graph structure

상관관계가 있는 변수를 측정하고, 가장 관련이 있는 것을 발견하려는 때가 있다. 이러한 구조는 그래프로 표현할 수 있다. 노드는 변수를 표현하고, 엣지는 변수 사이의 의존 관계를 표현한다.

1.3.4 Matrix completion

데이터가 손실되는 경우가 있다. 즉, 변수의 값을 모르는 경우가 발생할 수 있다. 따라서 이렇게 손실된 데이터에 타당한 값을 추정하는 것이며, 이것을 매트릭스 완성이라고 한다.

문제:

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다.

출력:

GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.

풀이방법:

https://ko.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98

GCD(n,k) = 1 는 n과 k가 서로수임을 의미하는 것이고, n과 서로소인 정수의 갯수를 세는 방법은 정수론에서 오일러 피 함수가 있다. 

오일러 피 함수를 간략히 설명하면 다음과 같다. 오일러 피 함수는 주어진 n의 소인수를 구한 뒤에, 각 소인수들의 (1-1/p)를 구해 n에 곱해주면 서로소의 갯수를 구할 수 있다. 따라서 이 함수를 python으로 구현하여 다음과 같이 계산하도록 한다.

문제링크:

https://www.acmicpc.net/problem/11689

문제:

두 자연수 N과 P를 가지고  다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자. 처음 출력하는 숫자는 N이고, 두 번째 이후 출력하는  숫자들은 N을 곱하고 P로 나눈 나머지를 구하는 과정을 반복하여 구한다. 즉, 먼저 N에 N을 곱하고, 이 수를 P로 나눈 나머지를 두 번째에 출력한다. 다음에는 이 나머지에 N을 곱하고 P로 나눈 나머지를 출력한다. 다음에는 이 나머지에 N을 곱한 후 P로 나눈 나머지를 출력한다. 이 과정을 계속 반복해보면 출력되는 숫자들에는 반복되는 부분이 있다.

예를 들어서, N=67, P=31인 경우를 생각해보자. 처음 출력되는 숫자는 67이고, 두 번째로 출력되는 숫자는 67×67 = 4489를 31로 나눈 나머지 25이다. 다음에는 25×67 = 1675를 31로 나눈 나머지 1, 다음에는 1×67 = 67을 31로 나눈 나머지 5가 차례대로 출력된다. 다음에는 5×67 = 335를 31로 나눈 나머지 25가 출력되는데, 이 수는 이미 이전에 출력된 수이다. 이 과정을 그림으로 보이면 다음과 같다.

즉 이 과정을 반복하면, 처음 67을 제외하면 3개의 숫자 25, 1, 5가 계속 무한히 반복되게 된다.   또 다른 예로, N=9, P=3을 가지고 시작하면, 9×9 = 81이고 3으로 나눈 나머지는 0이며, 0×3 = 0이고 3으로 나눈 나머지도 0이기 때문에 처음 9를 제외하면 0이 무한히 반복되게 된다. 

N과 P를 입력받아 위와 같이 정의된 연산을 수행하였을 때,  반복되는 부분에 포함된 서로 다른 숫자의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 처음 시작하는 N과 P가 공백을 사이에 두고 주어진다. 단, 1 ≤ N ≤ 1,000, 2 ≤ P ≤ 97이다.  

출력:

첫째 줄에 반복되는 부분에 포함된 서로 다른 숫자의 개수를 출력한다.

풀이방법:

 while 반복문을 사용하여, 주어진 조건에 따라 계속해서 연산을 진행하다가 memory에 같은 같이 존재하면 반복문을 종료하는 방식으로 문제를 해결한다. 이 때, 싸이클이 반드시 처음 시작한 숫자로부터 시작되는 것이 아니기 때문에 종료된 숫자가 있는 인덱스를 찾아서 전체 memory에서 빼줌으로써 싸이클의 길이를 계산한다.

문제링크:

https://www.acmicpc.net/problem/2526

문제:

모눈종이에 다각형을 그리려고 한다. 그리는 방법은 모양수열로 표시된다. 모양수열은 1과 4사이의 숫자가 연속되어 나열된 것으로 1은 오른쪽으로, 2는 위쪽으로, 3은 왼쪽으로, 4는 아래쪽으로 한 칸씩 그리는 것을 말한다.

예를 들어 아래 그림의 다각형 (2)는 점 A에서 시작하여 화살표 방향으로 모양수열 1411433322를 따라서 그린 것이다. 다각형 (3)은 점 B에서 시작하여 화살표 방향으로 모양수열 3221411433을 따라서 그린 것이다. 또한 다각형(4)는 점 C에서 시작하여 화살표 방향으로 모양수열 4411123323을 따라서 그린 것이다. 다각형 (2), (3), (4)는 다각형 (1)과 같으므로 모양수열들 1411433322, 3221411433, 4411123323은 모두 같은 다각형을 그릴 수 있다. 단, 다각형이 회전된 것이나 뒤집어진 것은 같은 다각형이 아니다. 그러므로 아래 그림의 다각형 (5)와 (6)은 다각형 (1)과 다르다.

한 개의 표본 모양수열과 여러 모양수열들이 주어졌을 때 표본 모양수열과 같은 다각형을 그릴 수 있는 모양수열들을 모두 찾는 프로그램을 작성하시오.

입력:

첫째 줄에는 표본 모양수열의 길이(숫자의 개수)가 주어지고, 둘째 줄에는 표본 모양수열이 주어진다. 셋째 줄에는 모양수열의 개수가 주어지고 넷째 줄부터는 각 줄에 표본 모양수열과 같은 길이의 모양수열이 하나씩 주어진다. 단, 모양수열들의 개수는 최대 100 개이고 모양수열의 길이는 최대 50 이다. 모양수열의 각 숫자 사이에는 빈칸이 하나 있다.

출력:

첫째 줄에는 입력된 표본 모양수열과 같은 다각형을 그리는 모양수열들의 개수를 출력한다. 둘째 줄부터는 각 줄에 표본 모양수열과 같은 다각형을 그릴 수 있는 모양수열을 출력한다. 출력되는 모양수열의 숫자들은 한 칸 띄고 출력한다.

풀이방법:

발생할 수 있는 경우의 수는 크게 두 가지다. 첫번째는 시계방향으로 진행하는 방법, 혹은 반시계방향으로 진행하는 방법이다.

따라서 주어진 표본 모양수열이 있으면 그 모양을 반대로 진행시킨 것을 생성하고, 각각 deque의 rotate 기능을 사용하여 회전시켜서 모든 경우의 수를 만든다. 그리고 주어진 입력이 이 경우의 수에 존재한다면 출력하고, 그렇지 않다면 넘어가도록 한다.

문제링크:

https://www.acmicpc.net/problem/2641

문제:

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.

4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

입력:

입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 회원의 수만큼 붙어 있다. 마지막 줄에는 -1이 두 개 들어있다.

출력:

첫째 줄에는 회장 후보의 점수와 후보의 수를 출력하고, 두 번째 줄에는 회장 후보를 오름차순으로 모두 출력한다.

풀이방법:

'친구사이'라는 용어가 애매하게 정의되어 있어서 헷갈릴 수 있지만 자신을 제외한 다른 모든 회원과 친구가 되기 위해 필요한 최대 거리를 의미한다. 즉 '친구의 친구의 친구'는 그 사람과 내가 알기 위해서 필요한 다리의 수와 같다.

따라서 이 문제를 플로이드-와샬문제로 생각하여 해결한다. 플로이드-와샬로 친구가 되기 위해 필요한 사람의 수들을 모두 구한 뒤, 각 사람마다 제일 큰 값이 그 회원의 점수가 된다.

회장이 될 수 있는 사람은 그 점수들 중 가장 작은 사람이여야 하기 때문에 그 점수들 중에 min을 찾은 후 그 점수를 가지고 있는 사람들을 출력한다.

문제링크:

https://www.acmicpc.net/problem/2660

문제:

실수 a와 정수 b가 주어졌을 때, a의 b제곱을 정확하게 계산하는 프로그램을 작성하시오.

입력:

첫째 줄에 a와 b가 주어진다. (0 < a < 100, 1 ≤ b ≤ 100) a는 최대 소수점 9자리이며, 소수가 0으로 끝나는 경우는 없다. a는 항상 소수점이 포함되어 있다.

출력:

첫째 줄에 a의 b제곱을 출력한다.

풀이방법:

python은 부동 소수점 문제가 있기 때문에 특히 소숫점 계산이 더 어렵다는 문제점이 있다. 따라서 이러한 문제점을 해결하기 위해서 python에서는 Decimal이라는 자료구조를 제공한다. 소수를 스트링 형태로 만든 뒤에 이를 지수, 가수 부분으로 나누어서 연산을 하는 방법이다.

문제링크:

https://www.acmicpc.net/problem/10827

문제:

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.

3 7 5 2 6 1 4

아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.

3 7 4 5 2 6 1

이제, 7번 아이를 맨 뒤로 옮긴다.

3 4 5 2 6 1 7

다음 1번 아이를 맨 앞으로 옮긴다.

1 3 4 5 2 6 7

마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.

1 2 3 4 5 6 7

위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

출력:

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

풀이방법:

 N명의 아이들을 번호 순서대로 배치하기 위해 최소의 움직임을 구한다는 것은 LIS 문제와 같다. 가장 긴 부분 수열을 찾고, 그 수열에 속하지 않은 아이들만 움직이는 것이 최소 움직임일 것이기 때문이다.

 따라서 DP를 사용한 LIS 문제를 풀고, N에서 그 값을 빼주도록 한다.

문제링크:

https://www.acmicpc.net/problem/2631

문제:

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.

조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.

백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.

입력:

첫째 줄에 테스트 케이스의 수가 주어진다.

각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

출력:

각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.

풀이방법:

 greedy하게 문제를 풀어주도록 한다. 다만, greedy한 조건 내에 범위가 짧은(a와 b의 차가 작은) 것 부터 먼저 배치하도록 한다. (1,3), (1,2), (1,2) 의 경우 모두에게 책을 줄 수 있지만 추가 조건이 없다면 답이 2로 나올 수 있다.

문제링크:

https://www.acmicpc.net/problem/9576

문제:

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.

격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.

비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
   • 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
   • 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

입력:

첫째 줄에 N, M이 주어진다.

둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.

다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.

출력:

첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.

풀이방법:

 문제에서 주어진 명령어을 순서대로 진행하면 된다. 각 명령에서 다음과 같은 사항들을 주의하면 된다.

1. 구름이 이동할 때, 행1-행N, 열1-열N 은 연결되어 있기 때문에 % 명령어를 사용해서 구름을 이동시킨다.

2, 3. 이동한 구름의 위치를 새 배열에 담아서 +1과 이전 구름이 사라진다는 것을 구현한다.

4. 이동할 수 있는 대각선 위치에 물이 1이라도 있는지 확인하고 매번 +1한다.

5. 전체적으로 탐색을 하면서 물이 2 이상인지 확인한다.( 2,3에서 활용한 배열을 사용한다.)

문제링크:

https://www.acmicpc.net/problem/21610