Baekjoon Online Judge
[BOJ] 17828 : 문자열 화폐 (C++)
https://www.acmicpc.net/problem/17828 17828번: 문자열 화폐 첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다. www.acmicpc.net 걸린 시간 : 24분 6초 오류 코드 맨 처음, A와 Z를 하나하나 문자열에 더해가면서 했다. 뭔가 비효율적이라고 생각이 들었고, 역시나 시간초과였다. #include using namespace std; int N, X; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> X; if (N > X || N * 26 < X) { cout 0) { if..
[BOJ] 20058 : 마법사 상어와 파이어스톰 (C++)
https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 걸린 시간 : 59분 47초 소문제 3개 정도로 쪼갤 수 있는 구현 문제이다. 항상 구현에서 힘들었는데 이 문제를 비교적 쉽게 해결한 것 같아 마음이 놓인다... 알고리즘 소문제는 다음과 같이 나눌 수 있을 것이다. L 값에 따라 배열을 회전 회전한 후 3칸 이상의 얼음과 인접하지 않은 칸은 얼음의 양 감소 모든 마법이 끝나고 얼음의 총량과 연결 요소의 최대 크기 파악 하나하나..
[BOJ] 2636 : 치즈 (C++)
https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 걸린 시간 : 47분 43초 생각이 너무 안 나서 답답했던 문제였다. 공기와 닿은 부분을 어떻게 찾을까 고민을 많이 했지만, 결국 실행마다 공기를 모두 찾아주고, 치즈를 모두 탐색해서 구현하는 것이었다. 이렇게 매 실행마다 해도, 실행은 최대 50번이고, 배열의 크기가 최대 100이라서 가능하다는 것을 알아차려야 했다. 알고리즘 배열은 0 ~ N+1 까지 있고 0과 N+1 부분은 가장자리이다. 사진에서 X..
[BOJ] 2110 : 공유기 설치 (C++)
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 걸린 시간 : 45분 44초 문제와 조건을 보고 한참을 생각하다,,,,, 결국 알고리즘 분류를 보았다. 매개 변수 탐색 문제이다. 실제 코딩테스트 등에서 많이 나올지는 모르는 문제이다. 너무 특수한 경우에만 적용 가능하고 기발한 생각으로 풀어야 하기 때문에 열심히 할 유형은 아니라고 생각된다. 매개 변수 탐색 (Parametric Search) ..
[BOJ] 1339 : 단어 수학 (C++)
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 걸린 시간 : 17분 46초 아이디어 입력을 받으면서 알파벳들의 가중치를 설정해준다. ABC 가 들어오면 A의 가중치에 100, B의 가중치에 10, C의 가중치에 1을 추가해주는 식이다. 입력이 끝나면 가중치가 큰 알파벳 순으로 9부터 내려가면서 할당한다. 끝이다.... 어렵지는 않은 문제 Map을 Value 기준으로 정렬 여기서 가중치를 map으로 구현하는데, map은 key를 기준으로 ..
[BOJ] 3055 : 탈출 (C++)
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 걸린 시간 : 36분 36초 BFS를 투트랙으로 하는 문제이다. 비슷한 문제를 풀어본 적이 있는 것 같다.. 우선, 내 목적은 비버를 D의 위치로 가게 하는 것이다. 여기서 가는 길이 물에 잠겨있다면 이동이 불가능하다는 조건이 붙는다. 이 조건을 위해 물의 흐름의 위치를 (wdist배열) 미리 완성해놓고, 즉 어떤 지점에 물이 몇 초만에 오는지 미리 모두 계산해놓고 비버를 움직인다. 예를 들어, 어떤 지점에 ..
[BOJ] 1600 : 말이 되고픈 원숭이 (C++) with BFS
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 걸린 시간 : 47분 25초 알고리즘 아이디어 BFS의 응용판, 3차원으로 푸는 문제이다. 이와 유사한 문제가 꽤 있다. 대표적으로 벽 부수고 이동하기 문제이다. (검색 ㄱㄱ!) 벽 부수고 이동하기와 문제 조건이 거의 유사하다. 벽 부수고 이동하기 문제의 경우 벽을 부수는 행위를 할 수 있고, 말이 되고픈 원숭이 문제의 경우 말처럼 이동할 수 있는 것이다. 단순 BFS의 핵심은 어..
[BOJ] 2140: 지뢰찾기 (C++)
https://www.acmicpc.net/problem/2140 2140번: 지뢰찾기 지뢰찾기는 N×N에서 이뤄지는 게임이다. 보드의 곳곳에는 몇 개의 지뢰가 숨겨져 있고, 지뢰가 없는 칸에는 그 칸과 인접(상하좌우 및 대각선)해 있는 8개의 칸들에 몇 개의 지뢰가 숨겨져 있는 www.acmicpc.net 걸린 시간 : 40분 12초 간단한 그리디와 구현 문제이다. 코드는 좀 복잡해 보일 수 있지만 어렵지 않다. 파란색 부분을 처리한다. 꼭짓점 부분이 1이라면 지뢰가 있는 것이고, 0이라면 없는 것이다. 따라서 파란색 부분은 간단하게 처리할 수 있다. 빨간색 부분을 처리한다. 꼭짓점 부분을 제외한 가장자리 모서리 부분이다. 인덱스가 낮은 곳부터 처리하다 보면 각 지점이 결정된다. 위쪽 모서리를 보자. ..
[BOJ] 16236: 아기 상어 (C++)
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 걸린 시간 : 1시간 40분 구조체를 사용해 공부해가며 문제를 풀어서 오랜 시간이 걸렸다. 구조체를 이용한 operator의 재정의를 처음 했고, 처음 하다보니 여러 오류가 많아 오래 걸렸다. 문제의 흐름은 다음과 같다. 상어가 이동하지 못할 때까지 이동한다. 하나의 이동은 while문 몸체의 한 번의 실행이다. 한 번의 이동에서는 상어가 있는 지점에서부터 다른 이동할 수 있는 모든 지점까..
[BOJ] 3109: 빵집 (C++)
https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 걸린 시간 : 37분 55초 문제가 무슨 소리인지 생각하는데 조금 걸렸지만, 문제가 무슨 말을 하는지 이해하고, 가능한 경우를 생각해보면 어떤 방식으로 코딩해야 하는지는 쉽다. 제일 왼쪽부터 시작해서 제일 오른쪽까지 대각선 혹은 직진으로 진행하면서 가능한 경로를 모두 세면 되는 것이다. 제일 위쪽부터 생각하면서 모든 경로를 생각하면 된다. 하지만, 보통의 백트래킹 생각대로 하면 실패한다. 보통, 현재 상황에서 체..