백준) 내가 살게, 아냐 내가 살게 (INU 송년 코드페스티벌 2019)

https://www.acmicpc.net/problem/18229 18229번 내가 살게, 아냐 내가 살게

문제

N명이 서로 결제하겠다며 카드를 내밀고 있다. 사람들과 점원의 거리는 K이다. 처음으로 손을 K이상 뻗은 사람은 결제하게 되는 영예를 얻는다. 사람들은 다음과 같은 과정으로 손을 뻗는다. 1번 사람이 손을 A1,1만큼 뻗는다. → 2번 사람이 손을 A2,1만큼 뻗는다. → 3번 사람이 손을 A3,1만큼 뻗는다. → ...... → N번 사람이 손을 AN,1만큼 뻗는다. → 1번 사람이 손을 A1,2만큼 추가로 뻗는다. → 2번 사람이 손을 A2,2만큼 추가로 뻗는다. → ...... → N번 사람이 손을 AN,M만큼 추가로 뻗는다. 여기서 A는 2차원 배열의 형태로 입력으로 주어진다.

다시 말해, 1번부터 N번 사람까지 순서대로 손을 뻗는 것을 M번 반복하며, 각 순서에서 손을 뻗는 정도는 입력으로 주어진다.

이때, 가장 먼저 K이상 손을 뻗는 사람이 등장하는 순간 그 사람이 결제하며 상황이 종료된다. 항상 위 과정에서 손을 K이상 뻗는 사람이 존재하게 입력이 주어진다. 결제하게 되는 사람은 누구일까? 그리고 그 사람이 손을 뻗은 횟수는 몇 번일까?

입력

첫째 줄에 위에서 설명한 정수 N, M(1 ≤ N, M ≤ 100), K(1 ≤ K ≤ 10,000,000)가 공백으로 구분되어 주어진다.

둘째 줄부터 N개의 각 줄에는 M개의 정수가 공백으로 구분되어 주어지며, 입력의 i+1번째 줄의 j번째 수는 Ai,j(1 ≤ Ai,j ≤ 10,000,000)를 의미한다.

출력

첫째 줄에 결제한 사람이 누구인지, 그 사람이 손을 뻗은 횟수는 몇 번인지를 의미하는 정수를 공백으로 구분하여 출력한다.

예제 입력 1 

4 5 20
3 5 2 1 4
1 8 2 5 8
1 5 2 3 3
1 1 8 9 9

예제 출력 1 

2 5

각 순서에서 어떤 사람의 손을 뻗은 정도는 아래와 같이 변한다.

1번 사람 : 3 → 2번 : 1 → 3번 : 1 → 4번 : 1 →

1번 : 8 → 2번 : 9 → 3번 : 6 → 4번 : 2 →

1번 : 10 → 2번 : 11 → 3번 : 8 → 4번 : 10 →

1번 : 11 → 2번 : 16 → 3번 : 11 → 4번 : 19 →

1번 : 15 → 2번 : 24

여기서 2번이 결제하게 되며 상황은 종료된다. 이때, 2번이 손을 뻗은 횟수는 5번이다.

알고리즘

1. 팔 뻗는 정도의 배열인 a[i][j]를 i번째 사람이 뻗은 손 정도의 총합인 sum[i] 에다가 i를 바꿔가면서 더해준다.

2. sum[i]가 k를 넘어가게 되면 for문을 깨고 i+1(몇번째 사람)와 j+1(몇번만에 계산했는지)을 출력한다.

코드