Algorithm66 [백준] 2839 설탕 배달 c++ 문제 링크 https://www.acmicpc.net/problem/2839 KEY 3과 5중에 5로 나누어 떨어지게 하는 것이 최소가 된다. 그리디 풀이 그리디 풀이의 경우 가령 18이 주어졌을 때, 5로 먼저 나누어 떨어지는지 보고, 아니라면 3씩 빼준다.(+1) 15가 되었을 때 5로 나누어 떨어지므로, 나눈 몫만큼 더해주면 (+3) 총 4번으로 배달 할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include #include #include #include using namespace std; int N; int answer; int main() { cin >> N; while (N >= 0) { if (N % 5 .. 2023. 3. 15. [프로그래머스] 단어 변환 c++ 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43163# KEY 두 문자열의 요소가 1개만 다른지 확인하는 함수를 따로 작성했다. 처음에 방문 배열(visited)를 사용하지 않고 DFS로 풀이했는데, 테스트케이스 3번에서 시간초과가 발생했다. 결국 visited를 사용하여 방문했던 노드를 탐색하지 않는 과정을 추가 Code 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include #include #incl.. 2023. 3. 14. [백준] 16953 A->B c++ 문제 링크 https://www.acmicpc.net/problem/16953 KEY 일반 구현으로도 문제풀이가 가능하나, DFS를 이용할 때 더 쉽게 접근할 수 있다. 2를 곱하거나, 뒤에 1을 붙이는 경우 총 2가지경우를 모두 탐색한다. 자료형을 주의깊게 보자.. Code 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 #include #include #include #include #include using namespace std; long long A, B; int result = 999999999; void dfs(long long x, int cnt) { if (x > B) return; if (x == B.. 2023. 3. 13. [백준] 2644 촌수계산 c++ 문제 링크 https://www.acmicpc.net/problem/2644 KEY 두 노드 사이의 거리를 구하는 문제이므로, 하나의 노드를 기준으로 다른 노드에 도착할 때까지 거리를 증가시킨다. DFS풀이의 경우 재귀함수의 종료조건은 n번 순회를 끝낼 때로 정했다. 구하고자 하는 거리 배열을 0으로 초기화했기 때문에 방문하지 않은 노드의 경우 0이 된다. ◈ DFS풀이 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 38 39 40 41 42 #include #include #include #include #include using namespace std; const .. 2023. 3. 12. [백준] 1389 케빈 베이컨의 6단계 법칙 c++ 문제 링크 https://www.acmicpc.net/problem/1389 KEY N번까지의 노드를 하나씩 출발노드로 지정하면서 (노드, 이동거리)의 큐를 만들어 이동거리의 합을 구하면 된다. 테스트케이스에서 예를 들어보면 다음과 같다. 1번노드에서 출발했을 때 1번(1,0) -> 3번(3,1), 4번(4,1) -> 2번(2,2), 5번(5,2) 따라서 이동거리의 총 합은 0+1+1+2+2 = 6 이 과정을 1~N노드까지 반복수행 Code 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53.. 2023. 3. 10. [백준] 9663 N-Queen c++ 문제 링크 https://www.acmicpc.net/problem/9663 KEY 퀸을 서로 공격하지 않게 하기 위해서는 퀸을 같은 행, 열, 대각선에 놓지 않아야 한다. (0~마지막 행) 까지 모든 행을 조사하면서 에 맞는 퀸의 위치가 나올 경우 다음 행으로 넘어간다. 만약에 에 맞지 않을 경우 현재 행의 다음 열로 가서 에 부합하는지 확인한다. Code 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 #include #include using namespace std; const int MAX = 15; int n; i.. 2023. 3. 9. 이전 1 2 3 4 5 6 ··· 11 다음
