문제 무한 수열 A는 다음과 같다. A0 = 1 Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1) N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 3개의 정수 N, P, Q가 주어진다. 출력 첫째 줄에 AN을 출력한다. 제한 0 ≤ N ≤ 1012 2 ≤ P, Q ≤ 109 예제 입력 1 복사 7 2 3 예제 출력 1 복사 7 예제 입력 2 복사 0 2 3 예제 출력 2 복사 1 예제 입력 3 복사 10000000 3 3 예제 출력 3 복사 32768 예제 입력 4 복사 256 2 4 예제 출력 4 복사 89 예제 입력 5 복사 1 1000000 1000000 예제 출력 5 복사 2 힌트 ⌊x⌋는 x를 넘지 않는 가장 큰 정수이다. 접근 방법- 딕셔너리를 활용해 트리구..

문제 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 칸에 대해서 조사를 한다. 가장 처음에 양분은 모든 칸에 5만큼 들어있다. 매일 매일 넓은 땅을 보면서 뿌듯한 하루를 보내고 있던 어느 날 이런 생각이 들었다. 나무 재테크를 하자! 나무 재테크란 작은 묘목을 구매해 어느정도 키운 후 팔아서 수익을 ..

문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으..

문제 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와..

문제 N(1 ≤ N ≤ 100)마리의 들쥐들과 M(1 ≤ M ≤ 100)개의 땅굴이 있다. 각각의 들쥐는 2차원 평면상의 한 위치에 있고, 각각의 땅굴들도 2차원 평면상의 한 점에 위치한다. 들쥐들을 잡아먹는 매가 들쥐들을 습격했을 때, 쥐들은 매를 피하기 위해서 땅굴 속으로 숨을 수 있다. 모든 쥐들이 땅굴에 숨을 수 있다면 매에 잡아먹히는 쥐가 한 마리도 없겠지만, 각각의 땅굴에는 한 마리의 쥐만 들어갈 수 있을뿐더러 매가 도착하는 시간과 쥐들이 땅굴로 도망치는 속도가 있기 때문에 항상 모든 쥐들이 도망갈 수 있는 것은 아니다. 매는 현재를 기준으로 S(1 ≤ S ≤ 100)초가 지난 후에 지상에 도착한다. 각각의 들쥐들은 매 초당 V(1 ≤ V ≤ 100)만큼의 거리를 움직인다(즉 V가 쥐들의 초속..

문제 chogahui는 수열 arr을 이용해 나머지 놀이를 하고 있습니다. 조가희는 수열에 다음과 같은 연산을 할 수 있습니다. 수열 arr의 맨 뒤에 num을 추가합니다. 수열 arr의 맨 뒤에 있는 원소를 제거합니다. chogahui가 물어보는 질문은 다음과 같습니다. 수열 arr의 맨 뒤에서부터 최소 몇 개의 수를 선택해야, 이들을 mod로 나누었을 때 나머지가 0, ... , mod-1인 경우가 최소 한 번 이상 나타나는가? chogahui의 질문을 해결해 주세요. 입력 첫 번째 줄에는 쿼리의 수를 의미하는 정수 Q와 나누는 정수 mod 가 공백으로 구분되어 주어집니다. (1 ≤ Q ≤ 2×105, 1 ≤ mod ≤ 102) 이후 Q개의 줄에 걸쳐서, 다음 세 종류의 쿼리 중 하나가 주어집니다. ..