❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악수열 A의 크기 N (1 ≤ N ≤ 1,000,000)✏️ 문제풀이3 5 2 7예제 입력 1을 먼저 생각해봅시다.3은 5와 짝지어집니다.5는 7과 짝지어집니다.2는 7과 짝지어집니다.그래서 결과적으로 `5 7 7 -1` 이라는 답이 나옵니다.짝 지어짐, 짝을 찾음 이라는 개념에서 '스택'을 떠올리셔야 합니다. (관련문제: 9012 :: 괄호, 4949 :: 균형잡힌 세상)스택의 가장 위에 있는 값 (`top()`)보다 작은 값을 만나면 스택에 `push()` 됩니다.반면에 더 큰 값(`big` 이라고 할까요?)을 만나면 `big`보다 큰 값이 스택의 가장 위에 올 때까지 `pop()` 합니다. (없다면 스택이 비게 되겠지요)`pop()` 하면서 오큰수를 저..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악N개의 컴퓨터 ≤ 10,000, M개의 관계도 ≤ 100,000컴퓨터 번호는 1번부터 N번한 번에 가장 많이 해킹할 수 있는 컴퓨터 번호를 오름차순으로 (하나면 한개, 두 개 이상이면 오름차순으로)✏️ 문제풀이트리도 그래프의 일종임을 생각하면 어렵지 않게 접근법을 생각할 수 있습니다. 입력으로 들어오는 A, B는 'A가 B를 신뢰한다' = 'B를 해킹하면 A도 해킹할 수 있다' = B → A로 생각할 수 있습니다. 즉, 문제에서 말하는바와는 반대방향으로 간선이 만들어지는 겁니다. A가 B를 신뢰하지만, 간선은 B에서 A를 향하도록 만들어집니다 이렇게 간선을 이어서 트리를 형성했을 때, 한 번에 가장 많이 해킹할 수 있는 컴퓨터란, 해당 노드를 시점으로 DF..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악노드 개수 N ≤ 50입력: 0 ~ (N-1)번 노드의 부모 정보, 루트노드는 -1출력: 리프노드의 개수✏️ 문제풀이문제에 나와있지 않은 조건을 자신도 모르게 '당연히 그러겠지~'라고 생각하고 풀지 않기를 연습하기 좋은 문제입니다.(비슷한 문제로 2468 :: 안전영역이 있습니다.) 문제 어디에도 주어지는 노드가 '이진 트리'라는 정보가 없습니다. 예시로 주어지는 그림이 이진트리라 햇갈리기 정말 좋습니다. 정말로 트리를 구현할 필요는 없습니다.각 노드의 부모가 입력되므로 배열의 각 칸마다 자식노드의 번호들을 저장하면 됩니다.이때, 앞서 언급했듯이 이진트리가 아니기 때문에 각 칸마다 왼쪽/오른쪽 자식노드의 번호를 저장하기 위해 `std::vector>` 타입..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악가로, 세로 ≤ 100출력: 치즈가 모두 녹는데 걸리는 시간, 모두 녹기 직전에 남아있던 치즈 칸 개수✏️ 문제풀이시뮬레이션(구현) + DFS/BFS 문제로, 문제가 요구하는대로 그대로 구현하면 됩니다.하지만, 바로 코딩에 들어가지 마시고 순서대로 어떤 절차를 밟을지 간단하게나마 손코딩을 한 후 진행합시다.`while(치즈가 남아있는 동안)` - 전체 칸을 순회하며 치즈가 있는지 확인하는 함수가 필요합니다.`(0, 0)` 공기를 시작점으로 DFS 또는 BFS를 돌려서 치즈를 만나면 '녹았다' 표시를 합니다.`(0, 0)`은 무조건 공기입니다. 문제에 '가장자리에는 치즈가 없다'고 나와있기 때문입니다.이 과정이 끝나면, 공기와 맞닿은 치즈는 '녹았다' 표시가..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악세로 크기 N, 가로 크기 M (3 ≤ N, M ≤ 8)0은 빈 칸, 1은 벽, 2는 바이러스2 ≤ 바이러스 개수 ≤ 103 ≤ 빈 칸출력: 안전영역의 최대크기✏️ 문제풀이안전영역의 최대 크기를 구하기 위해서는 주어진 빈칸들 중 3칸을 선택할 수 있는 모든 경우의 수를 따져봐야 합니다.연구실 크기는 최대 8 × 8 = 64칸입니다.최악의 경우, 벽이 하나도 없고 바이러스가 2개 있다면, 3개의 벽을 세울 수 있는 경우는 62 × 61 × 60 = 약 22만충분히 모든 경우의 수를 계산할 수 있습니다. 로직은 다음과 같습니다.선택한 빈칸 3칸을 `1`로 만들어 벽을 세웁니다.DFS 또는 BFS를 이용해서 시뮬레이션을 돌립니다. 각 바이러스마다 갈 수 있는 모..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악100글자보다 짧은 문장 입력문장 입력 : `getline(cin, str)`온점 "." 하나 입력될 때까지 입력 반복균형 문자열이면 "yes", 아니면 "no"✏️ 문제풀이9012 :: 괄호 문제의 진화버전입니다.역시 괄호 / 짝 찾기 문제이므로 스택을 사용한다는 것을 떠올려야합니다. 소괄호는 소괄호끼리, 대괄호는 대괄호끼리 짝지어집니다.스택이 비어있거나, 여는 괄호 (`(` 또는 `[`)를 만났다면 스택에 `push()`하며 나아갑니다.닫는 괄호(`)` 또는 `]`)를 만났다면, 스택 가장 위에 있는 것과 짝을 이루는지 확인합니다.짝을 이루지 않는다면 더 볼 것도 없습니다. 해당 문장은 균형 문자열이 아닙니다.📝 코드#include using name..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악여러개의 테스트케이스 T입력: 2 ≤ 각 괄호문자열 길이 ≤ 50출력: 괄호문자열이면 "YES", 아니면 "NO"✏️ 문제풀이괄호, 짝을 찾는다 같은 표현은 '스택'을 생각합시다. 현재 스택이 비어있거나, 여는 소괄호(`(`)를 만나면 스택에 `push()` 하면서 나아갑니다.닫는 소괄호를 만나면스택 가장 위에 있는 괄호가 여는 소괄호(`(`)인지 확인합니다.맞다면, `pop()` 하고, 아니라면, 해당 문자열은 괄호 문자열이 아닙니다.문자열 끝까지 순회했는데, 스택이 비어있지 않고 무언가 남아있다면해당 문자열은 괄호 문자열이 아닙니다.📝 코드#include using namespace std;int main() { ios::sync_with_stdio(..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악입력: N ≤ 10,000출력: N번째 종말의 수✏️ 문제풀이함정문제입니다.0666, 1666, 2666, 3666, 4666, 5666,6660, 6661, …., 6669, 7666, 8666, 9666총 19개… 그게 10666부터 11666까지…이렇게 빠져들기 시작하면 이 문제의 함정에 빠진 것입니다 ㅎㅎ함정에 걸리는 가장 큰 이유는 N이 10,000까지 가능해 오버플로우가 될 수도 있다고 생각하기 때문입니다. 단순하게 666부터 카운팅하면서 1,000으로 나머지연산(`%`)한 것이 666인 수를 찾으면 됩니다.while (temp) { if (temp % 1000 == 666) { answer++; break; } temp..

https://www.acmicpc.net/source/88151964  ❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악득점 개수 1 ≤ N ≤ 100각 득점 정보는 문자열로 "mm:ss" 형식출력: 1번팀이 이기고 있던 시간, 2번팀이 이기고 있던 시간✏️ 문제풀이1. 시간(초)을 하나의 칸으로 생각하는 방법'분'과 '초' 서로 다른 단위가 있을 때는 어느 한 쪽 단위로, 되도록이면 작은 단위로 통일하는 것이 좋습니다.농구경기 48분을 초로 환산하면 2,880초이므로 전체 농구경기를 연속된 2,880칸으로 표현할 수 있습니다. 문자열 "mm:ss"가 주어졌을 때, `int` 타입의 초로 환산하는 방법은 다음과 같습니다.60 * stoi(line.substr(0, 2)) + stoi(line.subst..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악입력: 테스트 케이스 T입력: 각 테스트 케이스마다 정수 1 ≤ N ≤ 1,000,000,000출력: $N!$를 나타냈을 때 오른쪽 끝에 있는 0의 개수✏️ 문제풀이당연히 `int`든 `unsigned long long`이든 수의 범위를 가볍게 넘어가기 때문에 직접 계산하는 문제가 아닙니다 ㅎㅎㅎ 0을 만들기 위해서 필요한 '재료'는 2와 5가 있습니다.$N!$를 나열하는 과정에서 2, 4, 6, 8 ... 정말 많은 2가 생성됩니다. 즉, 2라는 재료는 넘쳐난다는 뜻입니다.따라서, 0을 만들기 위한 '핵심재료'는 5입니다. $N!$ 속에 5가 몇 개 있느냐에 따라 0의 개수가 결정됩니다.코드로 나타내면 정말 간단합니다.for (int i = 5; i N ..