#문제 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..
#문제 15663번: N과 M (9) https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #접근방법 N개의 자연수 중에서 M개를 고른 수열을 출력하면 된다. 단, 중복되는 수열을 여러 번 출력하면 안된다. 모든 경우의 수를 구하는 백트래킹 기법을 사용하면서 적절한 조건문을 추가하면 풀 수 있다. #풀이 #include #include using namespace std; int n,m; int arr[10]; int num[10]; int che..
#문제 2908번: 상수 https://www.acmicpc.net/problem/2908 2908번: 상수 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 www.acmicpc.net #접근방법 두 수를 입력받고 거꾸로 바꾼 다음 비교를 하면 된다. #풀이 #include int f(int x){ int ans = 0; for(int i=x;i;i/=10) ans = ans*10 + i%10; return ans; } int main(){ int a,b; scanf("%d %d",&a,&b); a = f(a); b = f(b); if(a>b) printf("%d\n..
#문제 2753번: 윤년 https://www.acmicpc.net/problem/2753 2753번: 윤년 연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력하는 프로그램을 작성하시오. 윤년은 연도가 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때이다. 예를 들어, 2012년은 4의 배수이면서 www.acmicpc.net #접근방법 윤년일 때의 조건문을 작성하여 윤년을 판단하면 된다. #풀이 #include int main(){ int n; scanf("%d",&n); if((n%4==0 && n%100!=0) || n%400==0) printf("1"); else printf("0"); return 0; } 윤년은 4의 배수이면서 100의 배수가 아닐 때(n%4==0 && n%1..
#문제 2742번: 기찍 N https://www.acmicpc.net/problem/2742 2742번: 기찍 N 자연수 N이 주어졌을 때, N부터 1까지 한 줄에 하나씩 출력하는 프로그램을 작성하시오. www.acmicpc.net #접근방법 n부터 1을 반복문을 통해 출력해주면 된다. #풀이 #include int main(){ int n; scanf("%d",&n); for(int i=n;i>=1;i--) printf("%d\n",i); return 0; } n을 입력받고 n부터 1까지 반복하는 반복문에서 i를 출력해주면 정답이다. #성능 #정리 반복문을 통해 n부터 1을 출력해주면 풀 수 있는 단순한 문제였다.
#문제 2741번: N 찍기 https://www.acmicpc.net/problem/2741 2741번: N 찍기 자연수 N이 주어졌을 때, 1부터 N까지 한 줄에 하나씩 출력하는 프로그램을 작성하시오. www.acmicpc.net #접근방법 1부터 n을 반복문을 통해 출력해주면 된다. #풀이 #include int main(){ int n; scanf("%d",&n); for(int i=1;i
#문제 11725번: 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net #접근방법 루트가 1인 트리에서 n-1개의 엣지가 주어질 때, 2 ~ n번 노드의 부모를 찾는 문제이다. 두 노드를 입력 받을 때, 두 노드가 서로 연결되어 있다는 표시를 하고 dfs(깊이 우선 탐색)으로 각 노드의 부모를 구해주면 된다. #풀이 #include #include using namespace std; vector v[100005]; int ans[100005]={1}; void dfs(int x){ for(..
