알고리즘 문제풀이/백준
-
[백준/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..
-
[백준/BOJ] 2293번 동전 1 (C++)알고리즘 문제풀이/백준 2020. 12. 21. 19:58
www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 유형의 문제입니다. 점화식을 도출해내기 위해서 동전의 종류가 1원, 2원, 5원이 있고 숫자 10을 만드는 경우의 수를 구한다고 했을 때 밑의 예시를 살펴보겠습니다. 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1번부터 10번까지 dp 테이블을 만들고, 동전 1원으로 만들 수있는 경우를 살펴보면 전부 1개입니다. 그렇다면 다음으로 1원과 2원을 이용한 경우는 어떻게 되는지 살펴보..
-
[백준/BOJ] 18353번 병사 배치하기 (C++)알고리즘 문제풀이/백준 2020. 12. 21. 17:02
www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 유형의 문제로 LIS를 활용하는 문제입니다. 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 하므로, 이를 뒤집어 오름차순으로 변경하고 LIS의 최대값을 구해 전체 병사의 수에서 빼주면 되는 문제입니다. #include #include #include using namespace std; int dp[2001]; int main(void) { ios_base::sync_with_s..