알고리즘 문제풀이/백준
-
[백준/BOJ] 17521번 Byte Coin (C++)알고리즘 문제풀이/백준 2020. 12. 18. 01:12
www.acmicpc.net/problem/17521 17521번: Byte Coin 입력은 표준입력을 사용한다. 첫 번째 줄에 요일 수를 나타내는 양의 정수 n과 초기 현금 W(1 ≤ n ≤ 15, 1 ≤ W ≤ 100,000)가 주어진다. 다음 n 개의 줄에서, i번째 줄은 i일의 바이트 코인 가격을 나 www.acmicpc.net 그리디 문제 유형이라고 나오는데, 저는 DFS를 이용한 완전 탐색으로 매수/매도하는 모든 경우의 수를 구하고, 그 중에서 최대값을 구해 문제를 해결했습니다. 이때, 코인의 개수와 현금이 int 범위를 벗어날 수 있으므로 long long을 쓰는 것을 주의해야합니다. #include #include using namespace std; int n, w; long long a..
-
[백준/BOJ] 1463번 1로 만들기 (C++)알고리즘 문제풀이/백준 2020. 12. 18. 00:57
www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net BFS 혹은 DP로 해결할 수 있는 문제입니다. DP 풀이는 Bottom-Up 방식으로 1부터 n까지 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우중 최소값을 dp 테이블에 기록하고, 마지막에 dp[n]의 값을 리턴하면 됩니다. #include using namespace std; int dp[1000001]; // i를 1로 만들기 위해 필요한 연산 사용 횟수의 최소값 int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for..
-
[백준/BOJ] 18111번 마인크래프트 (C++)알고리즘 문제풀이/백준 2020. 12. 17. 16:55
www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 브루트 포스(완전 탐색) 유형의 문제였습니다. 블록의 높이가 최대 256에 2차원 배열이 최대 500x500이므로 시간복잡도가 256 x 500 x 500 = 64,000,000로 충분히 완전 탐색으로 해결할 수 있습니다. 인벤토리에 블록을 꺼내어 놓기, 블록을 제거하여 인벤토리에 넣기, 아무것도 안하기 세가지 경우를 고려해야하는데, 첫번째 경우에서 인벤토리가 0보다 작은 경우까지 고려하다보니 너무 예외처리가..
-
[백준/BOJ] 14226번 이모티콘 (C++)알고리즘 문제풀이/백준 2020. 12. 15. 21:17
www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net BFS와 DP를 이용한 문제 (다시 풀기) 화면과 클립보드를 가진 2차원 visit 배열을 선언하여 방문 여부를 확인하고 그 값으로 시간을 기록하는 것이 포인트입니다. 또한 클립보드의 내용을 화면에 출력하는 과정에서 '화면 + 클립보드 < 입력값의 최대' 조건을 반드시 만족해야 런타임 에러가 발생하지 않습니다. #include #include #include using namespace std; int visit..
-
[백준/BOJ] 1525번 퍼즐 (C++)알고리즘 문제풀이/백준 2020. 12. 13. 18:01
www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 독특한 유형의 BFS 문제였습니다. (다시 풀기) 메모리 제한이 있기 때문에 3x3 2차원 배열에 입력값을 저장하지 않고 문자열을 이용해서 1차원으로 입력값을 저장하는 것이 포인트입니다. 예를들어 1 0 3 4 2 5 -> 1 0 3 4 2 5 6 7 8 6 7 8 6 위에처럼 2차원 배열을 1차원으로 저장하는 것입니다. 이러한 1차원 문자열과 걸린 시간을 큐에 집어 넣으면서 문자열 처리를 해주면 되는데, 이때 0의 인덱스가 어디 있는지 찾는 것이 중요합니다. 이 인덱스를 통해 3x3 배..
-
[백준/BOJ] 10989번 수 정렬하기 3 (C++)알고리즘 문제풀이/백준 2020. 12. 13. 14:49
www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 입력값이 최대 10,000,000 이라서 시간복잡도가 O(NlogN)인 병합정렬을 이용해서 문제를 먼저 해결했다가 메모리 초과가 발생했습니다. 그래서 시간 복잡도와 공간 복잡도 모두를 만족할 수 있는 방법이 무엇이 있을까 검색을 해본 결과 계수 정렬을 이용하면 이 문제를 해결할 수 있다는 것을 알게 되었습니다. #include #include using namespace std; vector v(10001); int main(v..
-
[백준/BOJ] 2469번 사다리 타기 (C++)알고리즘 문제풀이/백준 2020. 12. 12. 16:12
www.acmicpc.net/problem/2469 2469번: 사다리 타기 첫 줄에는 참가한 사람의 수 k가 나온다(3≤k≤26). 그 다음 줄에는 가로 막대가 놓일 전체 가로 줄의 수를 나타내는 n이 나온다(3≤n≤1,000). 그리고 세 번째 줄에는 사다리를 타고 난 후 결정된 참 www.acmicpc.net 시작 알파벳에서 '?' 전까지, 결과 알파벳에서 '?' 전까지 알파벳의 순서를 계속 수정합니다. 위의 예시에선 최종적으로 '?' 전의 시작 알파벳과 '?' 전의 결과 알파벳은 다음과 같이 만들어집니다. 시작 알파벳 : [C, A, D, B, E, G, F, H, I, J] 결과 알파벳 : [C, A, B, D, G, E, F, H, J, I] 두 결과를 비교하여 문자가 같다면 '*', 순서가 ..
-
[백준/BOJ] 1049번 기타줄 (C++)알고리즘 문제풀이/백준 2020. 12. 12. 01:41
www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 간단한 수학(?) + 구현 문제입니다. 패키지와 단품 가격의 최소값을 구해 따로 저장하고 이를 이용하여 다음과 같이 가격을 구합니다. 1. 단품만 구매하는 경우 2. 단품 + 패키지를 구매하는 경우 3. 패키지만 구매하는 경우 세 가격 중 최소값을 구하면 됩니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); ..