#문제 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 #접근방법 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 이진 검색 트리를 전위 순회한 값이 입력값으로 들어올 때, 후위 순회한 결과를 출력해..
#문제 9498번: 시험 성적 https://www.acmicpc.net/problem/9498 9498번: 시험 성적 시험 점수를 입력받아 90 ~ 100점은 A, 80 ~ 89점은 B, 70 ~ 79점은 C, 60 ~ 69점은 D, 나머지 점수는 F를 출력하는 프로그램을 작성하시오. www.acmicpc.net #접근방법 정수 값을 입력 받고 적절한 조건문으로 시험 성적을 출력하면 된다. #풀이 #include int main(){ int x; char ans; scanf("%d",&x); if(x>=90) ans = 'A'; else if(x>=80) ans = 'B'; else if(x>=70) ans = 'C'; else if(x>=60) ans = 'D'; else ans = 'F'; prin..
#문제 3052번: 나머지 https://www.acmicpc.net/problem/3052 3052번: 나머지 각 수를 42로 나눈 나머지는 39, 40, 41, 0, 1, 2, 40, 41, 0, 1이다. 서로 다른 값은 6개가 있다. www.acmicpc.net #접근방법 수 10개를 입력받은 뒤, 이를 42로 나눈 나머지를 구한 다음 서로 다른 값이 몇 개 있는지 출력해야한다. 42칸의 배열을 만든 후, 42로 나눈 나머지 값의 배열인덱스에 기록을 하고 값이 들어있는 배열칸이 몇 개 있는지 출력하면 풀 수 있다. #풀이 #include int arr[42]; int main(){ int x; int ans = 0; for(int i=0;i
#문제 10998번: A x B https://www.acmicpc.net/problem/10998 10998번: A×B 두 정수 A와 B를 입력받은 다음, A×B를 출력하는 프로그램을 작성하시오. www.acmicpc.net #접근방법 A,B 정수값을 입력받은 후 곱셈한 값을 출력하면 된다. #풀이 #include int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d",a*b); return 0; } 정수 a,b를 입력받고 a*b를 출력하면 정답이다. #성능 #정리 정말 간단한 출력문제여서 설명할게 없다.
#문제 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
