분류 전체보기

[백준 1431번] 시리얼 번호 (C++)

https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net #include using namespace std; int s(const string & str){ // 자리수 합을 구하는 함수 int sum = 0; for(int i = 0; i = 48 && str[i] > n; string arr[50]; for(int i = 0; i > arr[i]; sort(arr..

[백준 11652번] 카드 (C++)

https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 카드 문제는 수의 범위가 너무 넓기 때문에 빈도수 배열로는 해결할 수 없습니다. 먼저, 같은 수가 연속되도록 주어진 정수들을 정렬하고, 배열의 처음부터 각 수의 빈도수를 계산하여 최대 빈도수를 구하면 문제를 해결할 수 있습니다. 또한 수의 범위가 int형의 범위를 넘어가므로 long long형 배열을 선언해야합니다. 아래는 전체 코드입니다. #include using namespace std..

[백준 1541번] 잃어버린 괄호 (C++)

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 읽어버린 괄호 문제는 분배법칙을 이용하여 해결할 수 있습니다. 문제에서 '+', '-'만으로 이루어진 문자열이 주어지기 때문에, 양수를 음수를 만들어서 최솟값을 만들 수 있습니다. 문자열의 왼쪽부터 시작하여, 음수를 만나면 다시 음수를 만날 때까지 음수 오른쪽의 양수들을 모두 음수로 만들면 식을 최솟값으로 만들 수 있습니다. 아래는 전체 코드입니다. #include using namespac..

[백준 11047번] 동전 0 (C++)

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전 0 문제는 Ai가 Ai-1의 배수이기 때문에 가치가 큰 동전부터 최대한 많이 선택하여 문제를 해결할 수 있습니다. 아래는 전체 코드입니다. #include using namespace std; int n, k, ans = INT_MAX; vector coin; int main(){ ios::sync_with_stdio(0); c..

[백준 11660번] 구간 합 구하기 5 (C++)

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 구간 합 구하기 5 문제는 행 누적 배열을 이용하여 해결할 수 있습니다. 계산의 편의성을 위해 가장 왼쪽에는 0을 넣어주었습니다. // 입력 배열 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 // 누적 배열 0 1 3 6 10 0 2 5 9 14 0 3 7 12 18 0 4 9 15 22 (x1, y1)부터 (x1, y2)까지의 합은 accu..

[백준 11725번] 트리의 부모 찾기 (C++)

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리의 부모 찾기 문제는 BFS를 이용하여 해결할 수 있습니다. 루트 노드부터 시작하여 인접한 노드를 방문하면, 현재 노드가 부모 노드가 되고, 인접한 노드가 자식 노드가 됩니다. 아래는 전체 코드입니다. #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector linked(n + 1); // 인접 리스트 for(int i =0; i ..

[백준 16953번] A → B (C++)

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net A → B 문제는 백트래킹으로 해결할 수 있습니다. 단, A와 B의 값이 최대 10억이고, 연산 적용시 21억을 초과할 수 있기 때문에 int형이 아닌 long long형을 사용해야합니다. 아래는 전체 코드입니다. #include using namespace std; long long a, b, ans = INT_MAX; void back(int th, long long n){ if(n == b){ ans = min(ans, (long long) th - 1); }else if(n < b){ back(th + 1, 2 *..

[백준 16928번] 뱀과 사다리 게임 (C++)

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 뱀과 사다리 게임은 1차원 배열, BFS를 이용하여 최단 거리를 계산하여 해결할 수 있습니다. 1번에서 시작하여 +6번까지를 방문합니다. 단, 사다리 또는 뱀이 있는 칸인 경우, 사다리 또는 뱀을 통해 이동한 칸도 방문해야 합니다. 아래는 전체 코드입니다. #include using namespace std; int board[101]; int vis..