SW

0. 제목 백준10825 국영수 BOJ 10825 국영수 C++ 10825 국영수 1. 문제 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다. www.acmicpc.net 2. 풀이 이름, 국어성적, 영어성적, 수학성적을 pair를 사용하여 묶어준다. sort함수에서 쓰일 정렬 기준 함수인 comp를 주의해서 구현하면 된다. 3. 코드 1 2 ..

0. 제목 백준 1182 부분수열의 합 BOJ 1182 부분수열의 합 C++ 1182 부분수열의 합 1. 문제 https://www.acmicpc.net/problem/1182 2. 풀이 브루트포스 방식으로 해결하였다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include using namespace std; int arr[20]; int N, S; int cnt; void dfs(int i, int sum){ if(i == N) return; if(sum + arr[i] == S) cnt++; dfs(i + 1, sum); dfs(i + 1, sum + arr[i]); } int mai..

0. 제목 백준 1987 알파벳 BOJ 1987 알파벳 C++ 1987 알파벳 1. 문제 https://www.acmicpc.net/problem/1987 2. 풀이 DFS와 백트래킹을 사용하는 문제이다. 방문 여부를 체크할 때 A~Z, 총 26개의 인덱스를 가진다. 상하좌우 이동하며, 방문하지 않았다면 true로 체크한다. 방문한적이 있다면 무시하고 넘어간다. 가장 깊게 들어간 최댓값이 정답이다. 3. 코드 #include #include #include #include using namespace std; char arr[21][21]; bool visitedAlpha[26];//A~Z int R, C; int dx[4] = {0,1,0,-1}; int dy[4] = {1,0,-1,0}; int df..

0. 제목 백준 1759 암호 만들기 BOJ 1759 암호 만들기 C++ 1759 암호 만들기 1. 문제 https://www.acmicpc.net/problem/1759 2. 풀이 브루트포스를 이용하여 푸는 문제이다. 모음과 자음을 따로 입력받고 벡터에 각각 저장한다. visited는 map으로 설정하였고 해당 string에 방문한적이 있으면 true, 없으면 false를 저장한다. 최소 한개의 모음과 최소 두개의 자음이 포함되어야 하므로 그 조건에 맞고 길이가 길이조건인 L과 같다면 해당 문자열을 사전순으로 정렬하고 visited.count(s)가 false이면 즉, 방문한적이 없으면 result에 push 해주고 return 한다. 만약, 요구하는 길이인 L과 길이가 같지만 자음, 모음 조건을 만족..

0. 제목 백준 1525 퍼즐 BOJ 1525 퍼즐 C++ 1525 퍼즐 1. 문제 https://www.acmicpc.net/problem/1525 2. 풀이 이 문제는 브루트포스와 BFS를 사용하는 문제였다. 아홉개의 칸 순서대로 이어지는 숫자로 표현할 것이기 때문에 0을 9로 바꿔주고 시작한다. 정수를 입력받으면서 start라는 변수에 9자리 수를 저장한다. key, value쌍을 가지고 있는 map을 사용하여 dist를 선언한다. dist[x]는 x까지 움직인 횟수를 뜻한다. BFS를 사용하기 위해 큐를 선언하고 큐가 빌때까지 반복한다. 큐의 맨 앞에 있는 정수를 문자열로 만들어준다. 그 후 pop을 하고 9가 저장되어 있는 인덱스를 찾는다. 찾은 인덱스를 이용하여 x좌표와 y좌표를 찾는다. 미로..

0. 제목 백준 1697 숨바꼭질 BOJ 1697 숨바꼭질 C++ 1697 숨바꼭질 1. 문제 https://www.acmicpc.net/problem/1697 2. 풀이 완전탐색을 푸는데에 5가지 방법이 있다. brute force(N중 for문) 순열 BFS(최소를 구하는 문제) 비트마스크 백트래킹 이 문제는 BFS를 사용하여 푼다. 현재위치와 현재까지 걸린 시간을 큐에 넣고 조건을 확인해가며 push, pop을 반복한다. 그렇게 반복문을 돌다가 현재위치가 동생이 있는 위치와 같아지게 되면 bfs함수는 현재까지 걸린시간을 반환한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33..

0. 제목 백준 10819 차이를 최대로 BOJ 10819 차이를 최대로 C++ 10819 차이를 최대로 1. 문제 https://www.acmicpc.net/problem/10819 2. 풀이 next_permutation 이라는 STL 함수를 사용하면 된다. next_permutation은 순열의 순서를 바꿔주고 순열이 최종적으로 끝나면(완전하게 역순이 되면) 다시 원래 순서대로 바꾼 뒤 false를 반환해준다. 예를 들어, 1 2 3 4 -> 1 2 4 3 -> 1 3 2 4 -> 1 3 4 2 -> ... -> 4 3 2 1 -> (false반환)1 2 3 4 그리고 처음에 무조건 실행을 하는 do~while문을 사용하였다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

0. 제목 백준 6378 디지털 루트 BOJ 6378 디지털 루트 C++ 6378 디지털 루트 1. 문제 https://www.acmicpc.net/problem/6378 2. 풀이 이 문제의 핵심은 수가 최대 1000자리라는 것이다. int 는 불가능하고 long long 마저도 불가능하다. 따라서 문자열로 입력받는다. 그 후 한자리수가 될 때까지 반복적으로 조건에 따라 계산을 한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #include using namespace std; int main(int argc, const char * argv[]) { string s; int s..

0. 제목 백준 2225 합분해 BOJ 2225 합분해 C++ 2225 합분해 1. 문제 https://www.acmicpc.net/problem/2225 2. 풀이 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다. dp를 이용하였고 dp[K][N]의 의미는 K개의 수로 N을 만드는 경우의 수이다. 예를 들어, dp[3][30]을 구한다고 해보자. 3개로 30을 만들어야 하는 경우이고, 마지막에 더하는 수가 0이라면 2개로 30을 만드는 경우가 나올테고, 마지막에 더하는 수가 1이라면 2개로 29를 만드는 경우가 나올테고, 마지막에 더하는 수가 2라면 2개로 28을 만드는 경우가 나올테다. 위와 같이 쭉 나열해보면 다음과 같은 점화식이 나온다. dp[i][j] = dp..

0. 제목 백준 9461 파도반 수열 BOJ 9461 파도반 수열 C++ 9461 파도반 수열 1. 문제 https://www.acmicpc.net/problem/9461 2. 풀이 점화식을 찾으면 쉽게 풀리는 문제이다. 두가지 점화식으로 풀리는데 다음과 같다. dp[i] = dp[i-2] + dp[i-3] dp[i] = dp[i-1] + dp[i-5] 두가지 중 하나로 코드를 짜면 정답이다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; int main(int argc, const char * argv[]) { int T, N; long int dp[101] = {0}; cin >> ..