www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이를 사용하는 문제지만 map을 활용해서 접두사 트리를 만들고 전화번호를 만드는 중에 이미 존재하는 전화번호가 있다면 YES 아니면 NO를 출력해주면 된다. map을 로 선언하고 string 부분은 전화번호, bool 부분은 완성된 전화번호인지? 를 판단하는 변수다 이런 식으로 처리해줘서 중간에 2가 나온다면 접두사에 완전한 전화번호가 존재한다는 뜻이니 NO를 출력해주면 된다. 1 2..

www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 간단한 1차원 BFS 문제인데 fill 배열로 초기화할 때 1000001으로 초기화해줘야 하는데 1000000으로 초기화해서 계속 틀렸다 ㅜㅜ;; 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 #include #include using namespace std; int f, s, g, u, d,..

소수를 구하는 여러 알고리즘들이 있지만 그중에서 자주 사용되는 것은 에라토스테네스의 체이다. 한번 틀을 짜놓고 외우면 이후에 쉽게 사용 가능하다. 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 #include #include using namespace std; vector sieve; void era(int n) { sieve.resize(n + 1, true); sieve[0] = sieve[1] = false; for (int i = 2; i * i n; era(n); for (int i = 2; i

www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 파일을 합칠 수 있는데 합치는데 드는 비용의 누적 합 중 최소가 되는 값이 정답이 된다. 재귀적으로 접근하면 그나마 쉽게 해 볼 수 있는데 그래도 어렵다.. 위 사진처럼 진행하는데 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다 연속이 되야 하기 때문에 따로 정렬이나 부분을 나누어서 접근하면 틀린다. d [i][j]..

www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net DP를 연습하던 중에 재미있는 풀이로 풀 수 있어서 가져와 봤다. k가 존재하면 (0, 0)에서 k가 존재하는 인덱스 (i, j)까지 의 길 찾기 경우의 수 \(nCk\)로 구하고 그 k에서 (n - 1, m - 1)까지의 경우의수를 또 구하면 된다. 나이브하게 풀면 오버플로가 나고 dp테이블에 조합을 저장해 두고 풀어야 한다. 1 2 3 4 5 6 7 8 9 10 11 1..

www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS를 하면서 회전이 총 몇 번 일어났는지 체크해주면 되는데 처음엔 방향 dir 벡터를 선언하고 그 방향과 다르면 +1 해주는 식으로 접근했다가 더 좋은 풀이가 보여서 참고했다. 결국 일직선으로 얼마나 갈 수 있는지를 확인하는 게 중요한데 BFS로 범위를 체크하는 부분에서 while문을 사용해서 범위가 끝날 때까지 직진하도록 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..