문제: www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제풀이 재귀 함수를 이용하여 문제를 풀었다. 일반적인 반복문으로 풀면 a^b는 연산 횟수에 의한 시간초과나 a^b 값의 크기로 인한 오버플로우가 일어날 수 있다. 코드 #include using namespace std; long long func(long long a, long long b, long long c){ if(b==1) return a % c; long long val = func(a,b/2,c); val = val * val % c; if(b%2==0..

문제: www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 문제풀이 불을 켤 때마다 bfs를 다시 해주어야 불을 켤 수 있는 좌표를 모두 찾을 수 있다. 코드 #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int board[101][101]; int visited[101][101]; int main()..

문제: www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제풀이 숨바꼭질 시리즈 문제, 일차원 직선에서의 BFS로 시작점(N)에서 동생(K)까지의 최단거리를 구하는 문제이다. 다른 숨바꼭질 문제와 다르게 수빈이의 경로도 출력해주어야 하기 때문에 dist배열을 2차원으로 선언하여 점마다 현재 점의 직전 점을 저장하였다. 마지막에 동생(K)에 도착하면 K부터 N까지 경로를 역으로 추적하여 벡터에 저장 후 순서대로 출력했다. 코드..

문제: www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제풀이 BFS 알고리즘 문제이다. 백준 2206번인 벽 부수고 이동하기 문제와 상당히 유사하다. 다른 점은 2206번은 능력을 한 번만 쓸 수 있지만 1600번은 능력을 K번 쓸 수 있다. 때문에 3차원 dist 배열을 K+1개만큼 선언해야 한다. 코드 #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int..

문제: www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 문제풀이 3차원에서 BFS 알고리즘으로 최단거리를 구하는 문제이다. 3차원 좌표를 표현하기 위해 tuple을 사용했다. 코드 #include #include #include using namespace std; int dz[6] = {-1,1,0,0,0,0}; int dx[6] = {0,0,-1,1,0,0}; int dy[6] = {0,0,0,0,-1,1}; string board[30][30]; int di..

문제: www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제풀이 일차원 직선에서 BFS 알고리즘으로 동생(K)까지의 최단거리를 구하는 문제이다. 주의할 점은 수빈이가 걸을 때(X-1, X+1) 1초의 시간이 걸리고 순간이동(X*2)할 때에는 시간이 들지 않는다는 점이다. 그래서 큐에 다음 점을 PUSH할때 순간이동을 한 점을 먼저 넣어줘야 최단시간을 구할 수 있다. EX) INPUT OUTPUT 걷는 것을 먼저 큐에 넣었을때..