1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1. 문제 설명 암호의 조건을 다시 정리하면 아래와 같다. 1개 이상의 모음이 있어야 함 2개 이상의 자음이 있어야 함 암호를 이루는 알파벳이 증가하는 순서일 것 2. 구현 아이디어 1 - 시간 초과 구현 문제라고 생각하고, 순열을 구할 때 사용하는 next_permutation을 활용하여 문제에 주어진 조건대로 구현하였다. 하지만 결과는 시간 초과 🥲 #include using namespace std; int l, c; vector v; char vowel[5] ..

1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 이전에 파이썬으로 푼 적이 있는 문제인데 데이터 추가로 재채점이 된 이후 시간초과로 틀린 문제 처리되어 이번에 C++로 다시 풀어보았다! 1. 문제 설명 예제 입력 1의 경우 C-A-D, 예제 입력 2의 경우 H-A-D-G-J-F로 갈 경우 최대여서 각각 3, 6을 출력한다. 2. 구현 아이디어 1 - 맞았습니다 !! 최대로 움직일 수 있는 칸, 즉 가장 '깊게' 들어갈 수 있는 칸 수를 세어야 하므로 DFS를 사용해야 한다. 이미 지나온 알파벳인지..

1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다!! 힌트를 통해 직관적으로 BFS를 사용해서 영역의 최댓값을 구하면 되겠다고 생각할 수 있었다! 주어진 입력의 크기도 크지 않고, 특별한 예외 조건이 없어 일반적인 BFS 로직을 사용하여 문제를 해결할 수 있었다! BFS를 구현해야 하므로 큐를 사용해주었다. 예제 입력 1과 힌트에 나온 그림을 비교했을 때 왼쪽 상단이 (1, 1)이기 때문에 좌표가 0부터가 아닌 1부터..

15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 N의 최댓값이 3,000,000이고 k의 범위가 3,000이므로 시간 초과에 주의하여야 한다. 먼저 k개를 넣어두고, 앞에 있는 초밥을 빼고 새로운 초밥을 넣는다 → 덱 자료구조를 활용 key를 초밥의 종류, value를 초밥의 갯수로 저장하여 초밥의 존재 여부와 갯수를 계산하자. #include using namespace std; int sushi[3001] = {0}; // 초밥..

18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다 !! 문제에서 계속 언급한 것처럼 '최단 거리'를 구하는 문제이기 때문에 다익스트라 알고리즘 or 플로이드-와샬 알고리즘을 사용해야겠다고 생각할 수 있었다. 출발 도시 번호가 주어지고 특정 노드로부터 다른 노드의 최단 거리를 구해야 함 입력으로 주어지는 n, m, k가 각각 30만, 100만, 30만으로 작지 않음 1번만으로도 다익스트라 ..

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 틀렸습니다 문제를 풀면서 덩어리가 몇 개인지 구해야 한다는 점에서 BFS/DFS 문제임을 알 수 있었다. 위 사진에서 높이가 2인 빙산이 녹으면서 0이 되고, 높이가 4인 빙산은 2가 되었다. 모든 빙산은 다 같이 줄어드는 것이기 때문에 높이가 4인 빙산 주변의 0인 칸을 셀 때 2→0인 빙산이 포함되지 않도록 주의해야 한다 !! 문제를 풀기 위해 아래와 같은 풀이 과정을 떠올렸다. 1. 입력을 받으면서 빙산의 좌..