기로에 서다

문제 www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 문제 풀이 괄호를 사용하는 전형적인 스택문제이므로 여는 괄호를 만났을 때, 그 앞의 숫자 K값을 담는 스택(벡터)를 하나 사용한다. 문자열을 처음부터 탐색할 때 (숫자,숫자), (숫자,여는괄호)와 같이 연속된 두 문자의 종류에 따라 길이에 더해지는 값이 달라지므로 편의상 문자를 두 개씩 보기로한다. 해당 문자가 숫자일때, 스택(벡터)이 비어있다면 $Q$꼴이고 스택(벡터)이 비어있지 않다면 $K(Q)$..

문제 https://www.acmicpc.net/problem/17080 17080번: 결함 게임 첫째 줄에 돌의 개수 N이 주어진다. (1 ≤ N ≤ 5,000,000) www.acmicpc.net 문제 풀이 각 플레이어는 턴마다, 만약 현재 보드 위에 있는 돌탑 중 어딘가에 올릴 수 있는 돌이 남아있다면, 반드시 그러한 돌들 중 하나를 골라 올릴 수 있는 돌탑 중 원하는 돌탑 위에 올린다. 만약 어떤 돌탑에도 돌을 올릴 수 없다면, 남아있는 돌 중 아무거나 하나를 골라 보드 위에 새로운 돌탑의 바닥을 만든다. 모든 돌이 소진된 뒤, 돌탑의 개수가 홀수이면 선공이 이기며, 짝수이면 후공이 이긴다. 위 조건들을 생각하며 돌의 개수를 한 개씩 늘려보면 아래의 규칙을 찾을 수 있습니다. 1. k개의 돌을 둬..

문제 https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 문제 풀이 1. 정확하게 순위를 매길 수 있다는건 이길 수 있는 선수의 수와 만나면 지는 선수의 수를 안다는 것이고, 이들을 합했을 때 자신을 제외한 N-1명이라는 것입니다. 2. 모든 선수간의 승,패 관계의 관계는 N v 이고 v > w 이면 u > w) 각 선수의 이길 수 있는 선수의 수와 만나면 지는 선수의 수를 하나씩 올려주면됩니다. 코드 #include #include using namespace std; int in[101],out[101]; // in..

문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제 풀이 단순하게 시간복잡도를 생각해본다면 $O(C*M*s)$ = $O(10^9)$로 TLE가 남 따라서 상어의 움직임을 줄여야 했고 아래의 관찰을 통해 해결함 (상어 H가 같은 위치로 돌아오는데 걸리는 시간) = (오른쪽으로 갔다가 돌아오는 시간) + (왼쪽으로 갔다가 돌아오는 시간) 이는 좌표를 우측 90도 방향으로 돌렸을때, (위,아래)로 움직이는 상어들도 동일하게..