❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력:N × M 미로, '붙어서' 들어오는 입력`scanf("%c")` 이용또는 `std::string`으로 한 줄 입력받은 후 `for()`로 처리또는 `std::string`으로 한 줄 입력받은 후 그대로 사용하기2 ≤ N, M ≤ 100출력: (N, M)에 도달하기 까지 밟아야 하는 최소 칸 수시작하는 칸, 도착하는 칸도 밟은 칸 수에 포함됩니다.✏️ 문제풀이최소 칸 수 = 최적해가중치 없음 (모든 칸이 한 칸 이동에 동일하게 한 칸 소요) = BFS 이용방문표시 후 시작점 queue에 `push`4방향 중 갈 수 있는 칸은 queue에 `push`하고 방문표시 합니다.queue가 빌 때까지 반복합니다.4방향 검사하기미로의 경계범위를 넘어서지 않았고..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 각 테스트케이스마다 2와 5로 나누어 떨어지지 않는 정수 N(1 ≤ N ≤ 10000)출력: 각 자릿수가 모두 1로만 이루어진 n의 배수의 자릿수✏️ 문제풀이[Tip] 정해지지 않은 입력 개수 입력받기 = `while (cin >> n)` 1. 증명하기이 문제는 정답을 정수 자료형에(`int`(12자리), `unsigned long long`(20자리)) 담을 수 없습니다.따라서 구해야하는 답인 '자릿수'에 집중해봅시다. $x$가 n의 배수라는 뜻은, $x \pmod n = 0$ 이라는 뜻입니다.그리고, 모듈로 연산(`%`)은 분배법칙이 성립합니다. $x \pmod n = 0$ 이고, $x$를 이전 규칙으로 표현하면 $((x\div10) - 1) ..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 2,147,483,647 이하의 자연수 A, B, C출력: A를 B번 곱한 수를 C로 나눈 나머지  ($A^B \pmod C$)✏️ 문제풀이첫 시도 :: 잘못된 접근나누는 수에 따라 나머지가 반복되는 성질이 있는 일부 수가 있는데, 모든 수가 그럴 것이라 생각하고 풀었습니다.그러나, 반드시 모든 수가 나머지가 반복되진 않습니다.ull A, B, C, result = 1;cin >> A >> B >> C;set s;while (B--) { result = (result * A) % C; if (s.find(result) != s.end()) break; s.insert(result);}cout `std::set`을 이용해서, 나머지가 반복될 때 멈춥..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 'A', 'B'로만 이뤄진 문자열, 길이 ≤ 100'000, 문자열 개수 N ≤ 100출력: 좋은 단어 개수✏️ 문제풀이'교차하지 않는다', '짝을 찾는다' 같은 용어는 먼저 '스택'을 떠올립시다.단어 내 문자를 하나씩 스택에 넣습니다.현재 top이 가리키는 문자와 똑같은 문자라면, 위 그림과 같이 서로 사라집니다.문자열 끝까지 탐색했는데,스택이 비어있다면, 좋은 단어입니다.스택이 비어있지 않다면, 좋은 단어가 아닙니다.📝 코드#include using namespace std;int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int N; cin >> N..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력재료개수: 1 ≤ N ≤ 15,000갑옷 1개 만드는 데 필요한 수: 1 ≤ M ≤ 10,000,000A[i] ≤ 100,000, 중복없음출력: 갑옷을 만들 수 있는 개수 ✏️ 문제풀이중복된 번호는 없기 때문에 A + B = M이 성립하는 재료 A, B를 발견하면 바로 선택하면 됩니다. (임의의 재료를 어느 재료와 조합하냐에 따라 만들 수 있는 갑옷 개수가 달라지거나 그렇지 않기 때문입니다.)하지만, 모든 경우의 수를 탐색하려면 $O(N^2)$이 소요되는데, N이 최대 15,000이므로 시간제한 2초내에 풀 수 없습니다.(사실 이 문제는 이렇게 풀어도 통과는 됩니다)더 효과적으로 탐색하려면, 투포인터를 사용하면 됩니다.재료 번호를 저장한 배열을 정렬한..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 알파벳 대문자로만 된 최대 50글자 문자열출력:팰린드롬을 만들 수 있다면, 팰린드롬을 출력하고팰린드롬을 만들 수 없다면, "I'm Sorry Hansoo"를 출력✏️ 문제풀이팰린드롬을 만들기 위해서는 반드시 문자열이 중간지점을 기점으로 대칭이어야 합니다.대칭이 되기 위해서는, 홀수번 등장하는 알파벳이 없거나 1개만 존재해야 합니다.즉, 홀수번 등장하는 문자가 2개 이상이라면, 해당 문자열은 팰린드롬을 만들 수 없습니다. 이런 맥락에서 보면, 팰린드롬은 다음과 같은 형태입니다.2회 이상 등장한 문자들을 각각 등장횟수 절반만큼 먼저 사전순으로 나열합니다.이렇게 나열한 문자열은 접두사(prefix)입니다. 나중에 이걸 뒤집어서 뒤에 붙이면, 모든 등장횟..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력:테스트케이스 T ≤ 100의상 개수 ≤ 30의상 한 종류는 하나만 입을 수 있음중복 이름 없음, 모두 소문자로 구성출력: 총 경우의 수✏️ 문제풀이 '의상종류'칸에는 하나의 '의상'만 들어갈 수 있습니다.'안 입는다, 안 쓴다' 라는 선택지를 포함하면 위 그림과 같습니다.중요한 것은 '의상종류'와 그 종류에 포함된 의상의 개수입니다. 또한, 의상은 중복해서 입력되지 않습니다.따라서 문자열 '의상종류'와 이에 포함된 의상 개수를 카운트 하기 위해 `std::map`를 사용하는 것이 적절하겠습니다.📝 코드#include using namespace std;int main() { ios::sync_with_stdio(false), cin.tie(null..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악1 ≤ 포켓몬의 개수 N, 문제의 개수 M ≤ 100,000포켓몬 이름 길이 ≤ 20문자열이 입력됐다면? 해당하는 번호 출력자연수가 입력됐다면? 해당하는 문자열 출력✏️ 문제풀이STL 자료구조를 활용할 수 있는지 묻는 기본적인 문제입니다.`std::string`을 key값으로 하는 `std::map`를 만들어 `std::string`이 입력됐을 때는 대응하는 `int`를 출력합니다.`int`를 key값으로 하는 `std::map`을 만들어 `int`가 입력됐을 때는 대응하는 `std::string`을 출력합니다.포켓몬을 입력 받을 때, 이름이 들어올지 번호가 들어올지 모르므로 우선 문자열로 입력 받습니다.만일 입력받은 문자열이 숫자라면, `stoi()` ..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력: 요소 개수 ≤ 100,000 (-100 ≤ 각 요소 ≤ 100)출력: 연속 K일 합의 최댓값✏️ 문제풀이최대 10만개의 입력이, 각 입력은 -100까지 가능하므로 초깃값은 -10,000,001로 잡는 것이 좋습니다.언제나 문제의 범위 바깥에 초깃값을 두도록 합시다.최댓값을 구해야하면 문제의 범위 바깥에 있는 최솟값으로 시작하고,최솟값을 구해야하면 문제의 범위 바깥에 있는 최댓값으로 시작하는게 중요합니다.1. 누적합을 이용한 풀이 'K'가 주어지기 때문에, 먼저 K일 까지의 합이 초깃값이 됩니다.2일-(K+1)일은 1일-K+1일 합에서 1일-1일 합을 뺀 것과 같다.3일-(K+2)일은 1일-K+2일 합에서 1일-2일 합을 뺀 것과 같다.4일-(K+..

❔문제 🔗문제링크 🔄 문제 및 입출력 조건 파악입력파일 개수 N ≤ 100각 파일명 길이 ≤ 100인 소문자패턴은 별표(*) 1개가 있는 길이 ≤ 100인 소문자출력패턴 일치 "DA"패턴 불일치 "NE"✏️ 문제풀이주어진 패턴은 별표(`*`)를 기준으로 (접두사) / (`*`) / (접미사) 세 가지 부분으로 나눌 수 있습니다. 입력된 파일명의앞부분('접두사'의 길이만큼)이 '접두사'와 일치해야 하고뒷부분('접미사'의 길이만큼)이 '접미사'와 일치하면 그 파일명은 패턴과 일치한다고 판단합니다.패턴 내에서 `*`의 위치(i.e. `pos`)를 찾으면접두사는 `[0~pos)`까지의 위치,접미사는 `[pos + 1, 패턴길이)`까지의 위치입니다.auto pos = pattern.find('*');patL ..