Patrick's Devlog

1. 개요 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 1-1. 설명 젤다의 전설 시리즈 주인공, 링크는 도둑 루피만 가득한 N x N 크기 동굴의 제일 위쪽에 있다. 젤다는 어떠한 이유로 인해 동굴안쪽까지 들어와버렸다. 그래서 제일 오른쪽 아래인 출구로 이동해야 하는 상황이다. 각 칸마다 도둑루피가 존재하는데, 이 칸을 지나면 해당 도둑루피 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 해 동굴 건너편까지 이동..

1. 개요 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 1-1. 설명 N x N의 표에 수 N^2개가 채워져 있다. 이때 채워진 수에는 특징이 있는데, 모든 수는 자신의 한칸 위에 있는 수보다는 크다. N x N 표가 주어졌을 때 N번째 큰수를 찾는 프로그램을 작성한다. 표에 채워진 수는 모두 다르다. 1-2. 제한 사항 - 첫 줄에 N이 주어지며, N은 1 이상 1,500 이하 - 다음 N개 줄에 각 줄마다 N개의 수가 주어지며, 이 수는 -10..

1. 개요 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1-1. 설명 10,000 이하 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되는 것중, 가장 짧은 길이를 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 N과 S가 주어지며, N은 1 이상 100,000 이하, S는 1 이상 100,000,000 이하 - 둘째 줄에는 수열이 주어짐 2. 구현 2-1..

1. 개요 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 1-1. 설명 이번 영어 시험에서 틀린 문제를 바탕으로 영단어를 암기하려고 한다. 그 과정에서 효율적으로 영단어를 외우기 위해 단어장을 만든다. 단어장의 단어순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다 - 자주 나오는 단어일수록 앞에 배치 - 해당 단어 길이가 길수록 앞에 배치 - 알파벳 사전 순으로 앞에 ..

1. 개요 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 1-1. 설명 비어있는 공집합 S가 주어졌을때, 원소 추가, 제거, 체크, 토글 등 여러 연산들을 수행하는 프로그램을 작성한다. 자세한 연산은 위의 링크를 참고한다. 1-2. 제한 사항 - 첫 줄에 수행해야 하는 연산 수 M이 주어지며, M은 1 이상 3,000,000 이하 - 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한줄에 하나씩 주어짐 2. 구현 2-1. 풀이 메모리가 매우 한정적이므, 비트마스킹을 이용해 풀었다..

1. 개요 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 1-1. 설명 A와 B로 이루어진 영단어를 통해 간단한 게임을 만들었다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀때는 다음과 같은 두가지 연산만 가능하다. - 문자열 뒤에 A 추가 - 문자열 뒤에 B를 추가 후 문자열을 뒤집음 주어진 조건을 이용해 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성한다..

1. 개요 https://www.acmicpc.net/problem/4659 4659번: 비밀번호 발음하기 좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp www.acmicpc.net 1-1. 설명 발음이 가능한 패스워드를 만드는 회사가 존재한다. 적당히 외우기 쉬우면서 안전하게 계정을 지킬 수 있는 비밀번호를 생성하기 위해 계획중이다. 높은 품질을 지닌 비밀번호 조건에 맞추어 비밀번호가 입력되었을 때, 높은 품질인지 확인하는 프로그램을 작성한다. 1-2. 제한 사항 - 여러개의 테스트 케이스로 이루어져 잇으며, 각 줄에 테스트할 패스워드가 주어짐 - 마지막 테..

1. 개요 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1-1. 설명 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고있다. 어느날 이 N명의 학생이 X번 마을에 모여 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있으며, i번째 길을 지나가는데 T_i의 시간을 소비한다. 각각 학생들은 파티에 참석하기 위해 걸어서 다시 마을로 돌아와야 한다. 이때, 최단 시간에 오고가기를 원할 때 ..