목록대학교/Algorithm (105)
차근차근
0. 제목 백준 14501 퇴사 BOJ 14501 퇴사 C++ 14501 퇴사 1. 문제 https://www.acmicpc.net/problem/14501 2. 풀이 dp방식을 사용하였으며 dp배열의 원소값을 0으로 모두 초기화 하고 시작하였다. 만약 일을 진행하는데 주어진 날보다 초과되면 dp[i+1] 값을 해주면 된다. 초기에 0으로 초기화해주었기 때문에 N이 초과되어도 0으로 갱신이 가능하다. 주어진 날 내에 끝낼 수 있다면 dp[i] = max(dp[i+T[i]] + P[i], dp[i+1]); 을 수행해준다. 위 점화식을 풀어 설명해보면 dp[i+T[i]]+P[i] 는 i번째 상담을 수행하면 T[i]일간 상담을 못하고 P[i]의 금액을 얻을 수 있고, dp[i+1]은 i번째 상담을 수행하지 않..
0. 제목 백준 2309 일곱 난쟁이 BOJ 2309 일곱 난쟁이 C++ 2309 일곱 난쟁이 1. 문제 https://www.acmicpc.net/problem/2309 2. 풀이 9명의 난쟁이중 2명을 제외한 나머지의 합을 모두 구한 후 100과 비교해본다. 2명을 제외한 나머지를 vector에 넣고 오름차순 정렬 후 출력한다. 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 34 35 36 37 #include #include #include using namespace std; int main(int argc, const char * argv[]) { int A[10]; in..
0. 제목 백준 1931 회의실배정 BOJ 1931 회의실배정 C++ 1931 회의실배정 1. 문제 https://www.acmicpc.net/problem/1931 2. 풀이 최대 회의수를 구해야하기 때문에 시작시간을 기준으로 잡으면 안되고 종료시간을 기준으로 잡아야 한다. 시작시간을 기준으로 잡아버리면 (1, 10)이 있다고 할 때 (3, 5), (6, 8)이 들어갈 수 없기 때문에 최대수를 구할 수 없다. 따라서 종료시간으로 오름차순 정렬을 한 후, 만약 종료시간이 같다면 시작시간 기준으로 오름차순 정렬을 해준다. 현재 종료시간보다 나중에 있는 시작시간이 있다면 회의수인 cnt를 1증가시키고 현재 종료시간을 나중에 있는 종료시간으로 갱신해준다. 반복문의 모든 loop를 끝낸 이후의 cnt가 최대 회..
0. 제목 백준 1783 병든 나이트 BOJ 1783 병든 나이트 C++ 1783 병든 나이트 1. 문제 https://www.acmicpc.net/problem/1783 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 #include using namespace std; int main(int argc, const char * argv[]) { int N, M; int result = 1; cin >> N >> M; if(N == 1) result = 1; else if(N == 2){ result = min(4, (M+1)/2); }else if(N >= 3){ i..
0. 제목 백준 2178 미로 탐색 BOJ 2178 미로 탐색 C++ 2178 미로 탐색 1. 문제 https://www.acmicpc.net/problem/2178 2. 풀이 최단거리 구하는 문제로 BFS를 사용하였다. make_pair를 사용하여 좌표쌍을 큐에 push하였다. BFS특성상 한단계씩 뻗어 나가기때문에 최단거리를 구하는데 적합하다. 큐에는 탐색할 좌표들을 담아놓는다. 큐에 있는 좌표가 더이상 주변의 탐색을 모두 끝낸 좌표일때 pop을 해준다. dist배열의 값이 0이면 아직 방문하지 않은 것이고 1 이상이면 방문을 했다는 것이고 1이상의 숫자는 dist[i][j] 에 오기까지 거친 블록의 수이다. 주의할 점으로는 입력을 받을때 연속해서 받기때문에 scanf("%1d", &arr[i][j]..
0. 제목 백준 7576 토마토 BOJ 7576 토마토 C++ 7576 토마토 1. 문제 https://www.acmicpc.net/problem/7576 2. 풀이 한단계씩 뻗어나가는 것이 효율적이라 판단하여 BFS를 사용하였다. make_pair를 사용하여 좌표쌍을 큐에 push하였다. 처음에 배열 값들을 입력받음과 동시에 그 값이 1이면 큐에 push 해주었다. 큐에는 탐색할 좌표들을 담아놓는다. 큐에 있는 좌표가 더이상 주변의 탐색을 모두 끝낸 좌표일때 pop을 해준다. 지금까지 풀었던 bfs문제들은 bfs함수내부에서 매개변수로 들어온 좌표들을 큐에 push 해주었다. 그러나 이 문제는 입력과 동시에 push 를 하였다. bfs함수내에서 한번의 루프를 돌때마다 한단계씩 뻗어나가고 서로 떨어져있는 ..
0. 제목 백준 2022 사다리 BOJ 2022 사다리 C++ 2022 사다리 1. 문제 https://www.acmicpc.net/problem/2133 2. 풀이 함수 func에서는 주어진 x와 y로 mid를 구한 후 기울기와 피타고라스정리를 이용하여 c에 관해 정리하였다. 수는 소수점 여섯째 자리까지 주어지므로 범위가 0.000001보다 큰동안 반복한다. 이분탐색을 통하여 범위롤 계속 갱신해주고 소수 여섯째자리의 정확도로 mid를 구한다. 절대/상대 오차는 0.001 까지 허용하므로 소수 셋째자리까지 출력해준다. 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 34 #inclu..
0. 제목 백준 2003 수들의 합 2 BOJ 2003 수들의 합 2 C++ 2003 수들의 합 2 1. 문제 https://www.acmicpc.net/problem/2003 2. 풀이 startIdx를 이용해 합의 시작점을 저장해준다. sum이 구하고자 하는 합 M과 같아지면 가능한 경우의 수인 cnt를 1증가시켜주고 M을 넘어가면 while문을 빠져나간다. 만약 while문에서 sum이 M보다 작고 startIdx가 배열의 마지막 원소를 지나치면 즉, N+1 이 되면 while문을 빠져나온다. cnt를 출력하면 정답니다. 그런데 이러한 문제는 투포인터를 사용한다고 하면 된다. 위 방법도 그와 비슷한 방법이지만 투포인터의 내용을 살려 또 다른 코드를 첨부하겠다. 투포인터 방식을 사용하면 위 방식보다 ..
0. 제목 백준 1789 수들의 합 BOJ 1789 수들의 합 C++ 1789 수들의 합 1. 문제 https://www.acmicpc.net/problem/1789 2. 풀이 while문이 돌면서 sum에 num을 더해준다. num을 하나 더해주었으므로 cnt도 1 더해준다. 만약 sum이 구하고자 하는 값 S보다 커지면 현재 cnt 에서 1을 빼준다. 예를 들면, 18을 구하고 싶었다면 1,2,3,4,5,6 까지 가면 21로 18보다 커지고 3을 빼면 되므로 1,2,4,5,6 즉, 5개가 나온다. num은 한 loop가 지날때 마다 1씩 증가한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include using names..
0. 제목 백준 1932 정수 삼각형 BOJ 1932 정수 삼각형 C++ 1932 정수 삼각형 1. 문제 https://www.acmicpc.net/problem/1932 2. 풀이 합이 최대가 되는 경로에 있는 수의 합을 출력하는 것이 문제이다. 2차원 배열 arr, dp를 할당하고 arr는 각 위치의 값이 담기고 dp는 그 위치로 갔을 때의 합이 담긴다. 그런데 합이 최대가 되어야 하므로 전 단계에서 즉, 윗 줄에서 왼쪽과 오른쪽중 큰 것을 선택해야 한다. 따라서 점화식은 다음과 같다. dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j] 그런데 좌표를 arr[1][1] 부터 시작하도록 설정하였으며 i-1 이 0이 나오는 dp[i][0]들은 0으로 초기화 시켜..