6246번 - 풍선 놀이 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 1169 | 763 | 685 | 65.802% |
문제
매년 가을 대전에서 열리는 대학생 프로그래밍 대회의 묘미 중 하나는 풍선 놀이이다. 시상식에서 스코어보드 공개를 기다리다가 심심해지면, 주위에 있는 풍선을 엮어서, 대회장을 가로지르는 긴 풍선 줄을 만드는 것이다! 이 풍선을 아치형으로 단상 위에 올리면, 본인의 잉여로움을 참가자들에게 뽐낼 수 있는 기회가 생긴다.
심심해진 재현이와 한필이는 풍선 놀이를 위해서 기다란 풍선 줄을 가져왔다. 풍선 줄에는 풍선을 매달 수 있는 N개의 슬롯이 있으며, 각 슬롯은 1번부터 N번까지 번호가 붙어있다. 풍선 줄에, 한필이는 Q번에 걸쳐서 규칙적으로 풍선을 꽂았다. 예를 들면, ’1번 슬롯부터 3개씩 띄어서 풍선을 놓자’ 라고 한필이가 생각했다면, 1, 4, 7, 10, ... 번째 슬롯에 풍선을 놓으며, 슬롯의 번호가 N을 초과하면 풍선을 놓는 것을 그만둔다. 이미 풍선이 놓여진 슬롯은 건너 뛴다.
Q번에 걸친 풍선 설치가 끝난 후, 한필이는 어떤 슬롯들이 비어 있는 것을 확인했다. 이 슬롯을 메꾸는 풍선을 가져오기 위해서, 총 몇 개의 슬롯이 비었는지를 계산해주자.
입력
첫 번째 줄에 슬롯 수 N과 풍선들을 꽂는 횟수 Q가 주어진다. (1 ≤ N ≤ 10, 000, 1 ≤ Q ≤ 100)
이후 Q개의 줄에 풍선을 꽂는 방법이 주어진다. 방법은 두 정수 L과 I로 주어지며, ”L번 슬롯부터 I개씩 띄어서 풍선을 놓자” 라는 뜻이다. (1 ≤ L, I ≤ N)
출력
비어있는 슬롯의 개수를 출력하라.
예제 입력 1
30 3 1 3 3 7 1 4
예제 출력 1
13
힌트
초기 빈 풍선 줄은 다음과 같다.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
한필이가 1번 슬롯부터 3개씩 띄어서 R 풍선을 설치했다.
R . . R . . R . . R . . R . . R . . R . . R . . R . . R . .
3번 슬롯부터 7개씩 띄어서 B 풍선을 설치했다.
R . B R . . R . . R . . R . . R B . R . . R . B R . . R . .
1번 슬롯부터 4개씩 띄어서 D 풍선을 설치했다.
R . B R D . R . D R . . R . . R B . R . D R . B R . . R D .
최종적으로 13개의 슬롯이 빈다.
출처
Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO US Open 2007 Contest > Bronze 2번
High School > 경기과학고등학교 > 나는코더다 2016 송년대회 E번
- 문제를 번역한 사람: koosaga
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호