#문제 16953번: A → B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net #접근방법 A를 B로 바꾸려고 할 때 아래 2가지 연산을 하여 A를 B로 바꾸는데 필요한 연산의 최솟값을 구해야 한다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. 자료구조 queue를 사용하여 경우의 수를 구하면 풀 수 있다. #풀이 #include #include using namespace std; int main(){ int A,B; int ans = -1; queue q; scanf("%d %d",&A,&B); q.push(make_pair(A,1)); while(!q.emp..
#문제 11660번: 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net #접근방법 n*n의 배열에 숫자값이 있을 때, (x1,y1), (x2,y2)의 좌표가 들어오면 O(1)번만에 정답을 구해야 시간초과가 걸리지 않는다. 누적합을 시킨 뒤, 적절한 연산을 해주면 쉽게 풀 수 있다. #풀이 #include int arr[1030][1030]; int main(){ int n,m; int..
#문제 9465번: 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net #접근방법 2*n크기의 점수가 매겨져있는 스티커가 있다. 스티커를 때면 상 하 좌 우에있는 스티커들을 못쓰게 될 때, 땔 수 있는 스티커 점수의 최대값을 구하는 문제이다. 다이나믹 기법을 사용하면 풀 수 있다. #풀이 #include #include using namespace std; int arr[2][100005]; int main(){ int T,n,a..
#문제 5639번: 이진 검색 트리 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net #접근방법 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 이진 검색 트리를 전위 순회한 값이 입력값으로 들어올 때, 후위 순회한 결과를 출력해..
#문제 1991번: 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net #접근방법 먼저 입력값으로 트리를 만들고 재귀함수로 전위, 중위, 후위 순회한 결과를 출력하면 된다. #풀이 #include int arr[26][2]; void pre(int x){ if(x
#문제 1932번: 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net #접근방법 삼각형의 제일 밑층에서 위로 올라가면서 둘 중에 큰 값을 누적시키는 것을 반복하면 맨 위에 있는 곳이 정답이 된다. #풀이 #include #include using namespace std; int arr[505][505]; int main(){ int n; scanf("%d",&n); for(int i=0;i
#문제 1629번: 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net #접근방법 일반적으로 반복문을 돌면서 곱셈과 나머지연산을 하면 약 21억번의 반복을 하므로 시간초과가 걸린다. 따라서 O(n)번이 아닌 O(log n)번의 시간복잡도로 풀어야 된다. #풀이 #include int A,B,C; long long int f(long long int y){ if(y==1) return A%C; long long int k = f(y/2)%C; if(y%2==0) return k*k%C; else return ..
#문제 1149번: RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net #접근방법 거리에 있는 N개의 집들을 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 인접한 집이 서로 다른 색으로 칠하도록 하며 모든 집을 칠하는 비용의 최솟값을 구해야 한다. 이전 배열의 값을 계속 사용하는 다이나믹 프로그래밍 기법을 사용하여 최솟값을 누적시키면서 풀면 된다...
#문제 15666번: N과 M (12) https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #접근방법 N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 모든 경우의 수를 구하는 백트래킹 기법을 사용하면서 적절한 조건문을 추가하면 풀 수 있다. #풀이 #include #include using namespace std; int n,m; int arr[10]; int num[10]; voi..
