알고리즘 문제풀이
-
[백준/BOJ] 11508번 2+1 세일 (C++)알고리즘 문제풀이/백준 2020. 12. 27. 02:11
www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 쉬운 그리디 문제입니다. 가격을 기준으로 내림차순 정렬을 한 후, 3개씩 묶을 때 마지막 가격만 빼면 되므로, 현재 인덱스 번호 % 3 의 값이 2가 아닌 경우는 모두 더해주면 됩니다. #include #include #include using namespace std; int cmp(long long a, long long b) { // 내림차순 정렬 return a > b; } int main(v..
-
[백준/BOJ] 14247번 나무 자르기 (C++)알고리즘 문제풀이/백준 2020. 12. 26. 19:52
www.acmicpc.net/problem/14247 14247번: 나무 자르기 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 www.acmicpc.net 그리디 유형 문제입니다. 나무가 자라는 가중치 값을 기준으로 오름차순 정렬을 한 후, 가중치가 작은 값부터 나무를 자르면 해결할 수 있는 문제입니다. #include #include #include using namespace std; int cmp(pair a, pair b) { return a.second < b.second; // 가중치 값을 기준으로 오름차순 } int main(void) { ios_ba..
-
[백준/BOJ] 13305번 주유소 (C++)알고리즘 문제풀이/백준 2020. 12. 25. 21:40
www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 그리디 유형의 문제입니다. 왼쪽에서 오른쪽 순서대로 도로를 건너갈 때, 현재 비용이 가장 작은 곳의 값에 각 도시를 연결하는 도로의 길이를 곱한 값을 더해주면 되는 문제입니다. 이를 위해 최소힙을 사용하였고, 한 가지 주의할 점은 문제에서 비용과 길이의 입력값이 굉장히 크므로, 더해지는 과정에서 int의 범위를 벗어나는 것을 방지하기 위해 long long으로 선언해줬습니다. #include #i..
-
[백준/BOJ] 2138번 전구와 스위치 (C++)알고리즘 문제풀이/백준 2020. 12. 25. 16:27
www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1>start>>target; int answer = min(check(start, target, n, false), check(start, target, n, true)); answer == 2147000000 ? cout
-
[백준/BOJ] 9019번 DSLR (C++)알고리즘 문제풀이/백준 2020. 12. 23. 13:23
www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS 문제입니다. (다시 풀기) D연산과 S연산은 어렵지 않고, L연산과 R연산만 잘 처리해주면 되는데, 처음에는 현재 숫자를 문자열로 바꾸어 L연산인 경우는 맨 앞의 문자를 뒤로 보내고, R연산인 경우는 맨 뒤의 문자를 앞으로 보내게끔 구현하려 했으나 코드가 좀 복잡해질 것 같아서 mod 연산을 이용하여 구현해봤습니다. 예를들어 입력값이 1234라고 가정해봅시다. L연산과 R연산을 했을 때 결과..
-
[백준/BOJ] 1520번 내리막 길 (C++)알고리즘 문제풀이/백준 2020. 12. 23. 13:14
www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DFS + DP 문제 유형 1949번 문제와 비슷한 유형입니다. (트리 구조인 것을 제외하면) DFS만을 이용해 (0,0)부터 (m-1,n-1) 까지 갈 수 있는 경우의 수를 구하면 최대 4방향에 500x500의 시간복잡도 때문에 시간초과가 발생할 수 있습니다. 따라서 메모제이션을 사용하여 시간복잡도를 줄여야합니다. 먼저 DFS를 통해 도착점에 도달하면 1을 리턴하고, 다시 위로 올라가며 탐색을 시작하는데, 이때 이..
-
[백준/BOJ] 15671번 오델로 (C++)알고리즘 문제풀이/백준 2020. 12. 22. 21:27
www.acmicpc.net/problem/15671 15671번: 오델로 오델로(Othello)는 검은색, 또는 하얀색 작은 원판을 6x6의 판 위에 늘어놓는 보드 게임이다. 보통 일본에서는 オセロ(오세로), 국내에서는 오델로라 부르고 있다. 어원은 오셀로 희곡으로 오셀로의 www.acmicpc.net 오델로 자체가 뭔지 일단 알아야 쉽게 풀 수 있는 구현 문제입니다. (문제만으로 이해가 잘 안가면 링크를 참조하세요!) 홀수번째 순서는 흑색돌, 짝수번째 순서는 백색돌을 둔다고 설정합니다. 미리 8방향 배열을 만들고, 현재 돌은 두는 위치를 하나 정합니다. 어떤 돌을 바꿀 수 있나 탐색을 시작하는데 '.'을 만나거나, map 범위를 벗어나거나, 이미 방문한 경우는 돌의 색을 바꿀 수 없음을 의미합니다. ..
-
[백준/BOJ] 4539번 반올림 (C++)알고리즘 문제풀이/백준 2020. 12. 22. 21:22
www.acmicpc.net/problem/4539 4539번: 반올림 정수 x가 주어졌을 때, 10보다 크다면, 1의 자리에서 반올림하고, 결과가 100보다 크면, 10의 자리에서 반올림하고, 1000보다 크면, 100의 자리에서 반올림하고... 이와 같이 계속 반올림하는 프로그램 www.acmicpc.net 입력값의 최대가 99999999이므로, 그냥 직관적으로, 쌩구현으로 쉽게 구현할 수 있는 문제입니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin>>n; while(n--) { int num; cin>>num; if(num >= 10) { num = (num..