#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll A, B, C;
ll rec(ll a, ll b, ll c){
if(b == 1) return a % c; // a가 c보다 클 수 있기 때문에 a % c를 반환.
ll val = rec(a, b/2, c);
val = val * val % c;
if(b%2 == 0) return val;
return val * a % c; // b가 홀수라면 *a %c 를 한 번 더 수행.
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> A >> B >> C;
cout << rec(A, B, C);
return 0;
}
리뷰
재귀를 공부하면서 푼 문제다. 곱셈을 하면 int의 범위를 넘어서기 때문에 long long 을 써야 한다. 단, b승을 알려면 b/2승을 제곱하면 된다는 것을 기반으로 코드를 짜야 한다.
12의 58승을 67로 나눈 나머지가 4라면, 12의 116승을 67로 나눈 나머지는 (4의 제곱) 즉, 16이 된다.
-> 58승을 계산할 수 있으면 116승을 계산할 수 있다.
-> k승을 계산할 수 있으면 2k승과 2k+1승도 O(1)에 계산할 수 있다.
이 두 문장은 참이다. 따라서 a의 임의의 지수승을 귀납적으로 계산할 수 있다.
귀납법의 일부를 코드로 바꿔보자.
func(a, b, c)는 func(a, b/2, c)를 기반으로 구할 수 있다.
using ll = long long;
ll func(ll a, ll b, ll c){
val = func(a, b/2, c);
val = val * a % c; // a를 곱하고 c로 나눈 나머지
}
// func(a, b, c)는 func(a, b/2, c)를 기반으로 구할 수 있다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll A, B, C;
ll rec(ll a, ll b, ll c){
if(b == 1) return a % c; // a가 c보다 클 수 있기 때문에 a % c를 반환.
ll val = rec(a, b/2, c);
val = val * val % c;
if(b%2 == 0) return val;
return val * a % c; // b가 홀수라면 *a %c 를 한 번 더 수행.
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> A >> B >> C;
cout << rec(A, B, C);
return 0;
}
// http://boj.kr/9c320eecca4b4958bd54977f83371a36
이 함수의 시간 복잡도는 b가 계속 절반씩 깎이니까 O(log b)이다.
그래서 문제의 시간 제한을 넉넉히 지킬 수 있다.
0x02 연습문제2 - 하노이 탑
두 번째 문제는 재귀 문제 중에 스테디셀러인 하노이탑 문제다.
온라인 게임으로 원판 3, 4, 5개일 때를 깨고 오자. 하노이탑 문제가 뭔지 감이 올 것이다.
//바킹독님코드 http://boj.kr/f2440915dca04aaa9aec759080516973
#include <bits/stdc++.h>
using namespace std;
void func(int a, int b, int n){
if(n == 1){
cout << a << ' ' << b << '\n';
return;
}
func(a, 6-a-b, n-1);
cout << a << ' ' << b << '\n';
func(6-a-b, b, n-1);
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int k;
cin >> k;
cout << (1<<k) - 1 << '\n'; // (1<<k)는 2의 k승이다.
func(1, 3, k);
}
0x03 연습문제3 - Z
하노이탑이 아리송하지만. 백준 1074번 Z문제를 읽어 보면 '또 뭔가..' 싶을 것이다.
꾹 참고 5분만 재귀 관점으로 고민해보자.
방문 순서가 어떤 식으로 매겨지냐면, 배열을 4등분 한 후에, 1,2,3,4 순으로 진행된다.
아래 그림에서 N=3일 때, 16x16 배열을 그려놓고. 4등분 해서 영역 1,2,3,4로 나눠놨다.
r=2, c=2 칸은 '영역1'에서' 12번째로 방문한다.
'영역1' 내부를 4등분으로 나누면, 영역 1, 2, 3에 포함된 0칸~11칸을 전부 방문하고, 12번째로 방문한 셈이다.
r=6, c=2 칸은 '영역3'에서 44번째로 방문한다.
'영역3'에 오기 전에는 이미 '영역1, 영역2'를 방문한다. '영역3'내부의 0칸~11칸을 전부 방문하고, 12번째로 방문한 셈이다.
뭔가 이전에 방문한 순서를 기반으로 다음 것을 구할 때 써먹을 수 있을 것 같다는 느낌이 조금 온다. (그저 느낌뿐..)
구현을 위해 단계적으로 생각해보자.
1. 함수의 정의
직관적으로 보이는 모양 대로 정의하면 된다. 2의 N승 배열에서, (r,c)를 방문하는 순서를 반환하는 함수.
이 값이 Int범위에 들어오는지 신경써줄 필요가 있는데, n은 15이하니까 int범위를 초과하지 않는다.
int func(int n, int r, int c)
2. base condition
n=0일 때 0을 반환하도록 하자.
n=0 일 때, return 0;
3. 재귀 식
각 상황에 따른 반환 값은 아래와 같다.
여기서 half는 한 변 길이의 절반, 즉 2의 n-1승이다.
(r,c)가 1번 영역일 때, return func(n-1, r, c);
(r,c)가 2번 영역일 때, return half*half + func(n-1, r, c-half);
(r,c)가 3번 영역일 때, return 2* half*half + func(n-1, r-half, c);
(r,c)가 4번 영역일 때, return 3* half*half + func(n-1, r-half, c-half);
아까 그림을 보며 확인한 12번째 방문한다는 것의 의미를 다시 보자.
12번째 방문한다는 것은0칸~11칸을 전부 방문하고, 12번째로 방문하는 것이다.
2의 2승 을 4등분한 영역에서, 2의 1승(2의 n-1승) 영역의 1,2,3영역을 모두 방문한 다음에 4영역을 방문하고 있는 것이다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502] =
{{1,1,1,0,1,0,0,0,0,0},
{1,0,0,0,1,0,0,0,0,0},
{1,1,1,0,1,0,0,0,0,0},
{1,1,0,0,1,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
queue<pair<int,int> > Q;
vis[0][0] = 1; // (0, 0)을 방문했다고 명시
Q.push({0,0}); // 큐에 시작점인 (0, 0)을 삽입.
while(!Q.empty()){
pair<int,int> cur = Q.front(); Q.pop();
cout << '(' << cur.X << ", " << cur.Y << ") -> ";
for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
if(vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
Q.push({nx,ny});
}
}
}
[중요] BFS 구현 시 자주 하는 실수
1. 시작점에 방문했다는 표시를 남기지 않는다. 방문 배열에 꼭 방문 표시를 남겨야 재방문 하지 않고 무한루프로 빠지지 않는다.
2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문 했다는 표시를 남겼다. 같은 칸이 큐에 여러번 들어가서 시간초과나 메모리 초과가 날 수 있다.
3. 이웃한 원소가 유효범위를 벗어났는지에 대한 체크를 잘못했다. 배열 인덱스가 음수가 되거나 유효범위를 넘어가면 런타임 에러가 난다.
미로를 저장하는 배열을 미로 -1로 초기화해두면 굳이 방문배열을 두지 않아도 방문여부를 확인할 수 있다.
// http://boj.kr/cd14bec9ecff461ab840f853ed0eb87f
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[102];
int dist[102][102];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> board[i];
for(int i = 0; i < n; i++) fill(dist[i],dist[i]+m,-1); // -1로 초기화한다
queue<pair<int,int> > Q;
Q.push({0,0});
dist[0][0] = 0;
while(!Q.empty()){
auto cur = Q.front(); Q.pop();
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 유효범위 확인
if(dist[nx][ny] >= 0 || board[nx][ny] != '1') continue; // 이미 방문했는지. 벽이 아닌지.
dist[nx][ny] = dist[cur.X][cur.Y]+1;
Q.push({nx,ny});
}
}
cout << dist[n-1][m-1]+1; // 문제의 특성상 거리+1이 정답
} // 바킹독님 코드
// http://boj.kr/ae38aa7eb7a44aca87e9d7928402d040
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[1002][1002];
int dist[1002][1002];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n;
queue<pair<int,int> > Q;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> board[i][j];
if(board[i][j] == 1) // 익은 토마토는 시작점이니까 큐에 넣는다.
Q.push({i,j});
if(board[i][j] == 0) // 아직 안익은 토마토는 -1 로 표시한다.
dist[i][j] = -1;
}
}
while(!Q.empty()){
auto cur = Q.front(); Q.pop();
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 유효한 범위인지?
if(dist[nx][ny] >= 0) continue; // 이미 방문.
dist[nx][ny] = dist[cur.X][cur.Y]+1;
Q.push({nx,ny});
}
}
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(dist[i][j] == -1){ // 아직 익지않은 토마토가 있으면? 실패.
cout << -1;
return 0;
}
ans = max(ans, dist[i][j]); // 가장 먼 거리.
}
}
cout << ans;
}
해결 과정
1. 입력 받으면서 익은토마토만 큐에 넣는다.
2. 익지 않은 토마토는 dist 배열값을 -1로 둔다. 토마토가 없는 빈칸은 dist 배열 값이 0이다.
// http://boj.kr/aed4ec552d844acd8853111179d5775d
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[1002];
int dist1[1002][1002]; // 불의 전파 시간
int dist2[1002][1002]; // 지훈이의 이동 시간
int n, m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i++){ // 모든 방문배열 -1로 초기화 하여 미방문 표시하기
fill(dist1[i], dist1[i]+m, -1);
fill(dist2[i], dist2[i]+m, -1);
}
for(int i = 0; i < n; i++)
cin >> board[i];
queue<pair<int,int> > Q1;
queue<pair<int,int> > Q2;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(board[i][j] == 'F'){ // 불이면 큐1에 푸시. 거리도 배열1에 0초기화.
Q1.push({i,j});
dist1[i][j] = 0;
}
if(board[i][j] == 'J'){ // 지훈이 시작점은 큐2에 푸시. 거리도 배열2에 0초기화.
Q2.push({i,j});
dist2[i][j] = 0;
}
}
}
// 불에 대한 BFS
while(!Q1.empty()){
auto cur = Q1.front(); Q1.pop();
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue; // 벽이거나 이미 방문했으면 지나감
dist1[nx][ny] = dist1[cur.X][cur.Y]+1;
Q1.push({nx,ny});
}
}
// 지훈이에 대한 BFS
while(!Q2.empty()){
auto cur = Q2.front(); Q2.pop();
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m){ // 범위를 벗어났다는 것은 탈출에 성공했다는 의미. 큐에 거리 순으로 들어가므로 최초에 탈출한 시간을 출력하면 됨.
cout << dist2[cur.X][cur.Y]+1;
return 0;
}
if(dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y]+1) continue; // 불의 전파 시간을 조건에 추가
dist2[nx][ny] = dist2[cur.X][cur.Y]+1;
Q2.push({nx,ny});
}
}
cout << "IMPOSSIBLE"; // 여기에 도달했다는 것은 탈출에 실패했음을 의미.
}
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
// 2805 나무자르기
long long n, m, num, answer;
vector<long long> v;
void bs(){
int start = 0;
int end = *max_element(v.begin(), v.end());
int mid = 0;
while(start <= end){
mid = (start+end)/2;
long long tempsum = 0;
for(int i=0; i <n; i++){
if(v[i]>mid) tempsum += (v[i]-mid);
}
if(tempsum >= m){ // 조건 만족시,
answer = mid;
start = mid+1;
}else{ // 덜 깎아야 함.
end = mid-1;
}
}
cout << answer;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> num;
v.push_back(num);
}
bs();
return 0;
}
리뷰
나무의 수와 높이가 꽤 크다. 나무는 백만개가 최대. 높이는 10억이 최대.
단순하게 절단기 높이를 0부터 10억까지 반복문으로 검사하기에는 시간이 오래걸린다. 10억 x 100만 이기 때문이다.
따라서 이분탐색으로 절단기의 높이를 찾는다. 이 때, 최소값은 0, 최대값은 나무중에서 제일 긴것을 기준점으로 잡는다.
이분 탐색의 중간값mid로 나무를 절단했을 때, 잘라낸 나무 누적 합(tempsum)이 기준값(m)을 만족시키면 답으로 저장해둔다. answer = mid;
기준값보다 잘라낸게 더 많으면, 덜 깎아야 하니깐 start = mid+1; 절단기의 높이를 높여야 덜 깎는다. 기준값보다 누적합이 작으면, 더 깎아야 하니까 end=mid-1; 절단기의 높이를 줄여야 더 많이 깎여나간다.
"절단기의 높이를 줄이면, 나무가 더 많이 깎여나가니까 tempsum이 증가한다" 처음에는 이 부분이 헷갈렸었다.
