본문 바로가기

백준

 (233)
[백준 / BOJ] 12791 Starman 문제 출처 : https://www.acmicpc.net/problem/12791 12791번: Starman 첫 번째 줄에 질의의 수 정수 Q(Q ≤ 100)가 주어진다. 이후 Q개의 줄에 질의 S, E(1 ≤ S ≤ E ≤ 2016)가 정수로 주어진다. www.acmicpc.net 쿼리의 수 Q와, 각 쿼리마다 S년(1월 1일) E년(12월 31일) 이 주어진다. S년 부터 E년까지 발매된, 전설적인 락 스타 David Bowie의 앨범을 출력하는 문제다. 풀이 구현 문제였다. 문제에서 주어진 앨범을 2차원 ArrayList에 집어넣고, 출력하는 방식으로 풀었다. 예를들어, David Bowie가 1973년에 AladdinSane 과 PinUps를 발매했으니, 2차원 배열에는 다음과 같이 저장한다. ..
[백준 / BOJ] 17281 ⚾ (야구) 문제 출처 : https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 게임은 N개의 이닝으로 이루어져있다. 우리는 9명이 선수가 각 이닝에 얻는점수를 알고있다. 각 선수의 순서를 적절히 배치하여 (1번부터 9번까지) 얻을수있는 최대 점수를 구하는 문제다. 풀이 완전탐색으로 푼 문제다. 모든 선수의 배치가능한 조합을 구한후, 구해진 조합을 토대로 점수를 구하면 된다. 선수는 9명이지만, 1..
[백준 / BOJ] 20925 메이플스토리 문제 출처 : https://www.acmicpc.net/problem/20925 20925번: 메이플스토리 첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다. 다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마 www.acmicpc.net 상원이는 메이플스토리를 할 것이다. 상원이의 캐릭터가 갈수있는 사냥터의 수 N 상원이가 사냥할 시간 T 가 주어지고, 이후, N개의 줄에 각 던전에 입장하는데 필요한 최소경험치와 시간당 주는 경험치가 주어진다. 상원이가 T시간동안 사냥했을때 얻을 수 있는 최대 경험치를 구하는 문제다. 풀이 dp로 푼 문제였다. 처음에..
[백준 / BOJ] 20924 트리의 기둥과 가지 문제 출처 : https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net N개의 노드와 N-1개의 간선으로 이루어진 트리가 있다. 이 트리의 루트를 타고 이동하다가, 처음으로 2개 이상의 노드가 연결된 노드가 발견될 경우, 이를 기가 노드라고 하며, 이전 경로를 기둥경로 라고 한다. 기가 노드에서시작해서 기둥 경로를 제외하고, 리프노드까지의 ..
[백준 / BOJ] 20922 겹치는 건 싫어 문제 출처 : https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net N개의 수가 있는 수열이 주어진다. 이 수열중 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 문제다. 풀이 투 포인터로 풀은 문제다. 최장 연속 부분 수열이기때문에, 답이 될수있는 수열은 모두 붙어있어야한다. 따라서, 투 포인터로 left,right값을 지정한 후에 탐색하면 2N시간만에 답을 구할 수 있다. 메인 소스코드 private int getLon..
[백준 / BOJ] 20921 그렇고 그런 사이 문제 출처 : https://www.acmicpc.net/problem/20921 20921번: 그렇고 그런 사이 정수 $N$, $K$가 주어진다. ($2 \leq N \leq 4\,242$, $0 \leq K \leq \frac{N(N-1)}{2}$) www.acmicpc.net 환주는 두명을 그렇고 그런 사이로 만드는데 전문가이다. 그렇고 그런 사이가 될려면, 다음 조건을 만족해야한다. (P(i)가 갖고있는 숫자가 P(i+a)보다 커야함) (단, a>0) 환주의 친구의수 N, 그렇고 그런 사이로 만들어야하는 쌍의수 K가 주어졌을때, 그렇고 그런 사이를 만드는 경우를 출력하는 문제다. 풀이 재밌는..? 문제였다. 문제를 처음 봤을때는 감이 잘 안잡혔는데,(dp라고 예상했었음) 문제의 예제를 직접 해보니..
[백준 / BOJ] 20920 영단어 암기는 괴로워 문제 출처 : 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 영어 단어장에 N개의 단어가 적혀있다. 화은이는 단어장에있는 N개의 단어들중 K개의 길이 이상의 단어를 다음 순서에따라 정렬할려고한다. 1. 자주 나오는 단어순으로 정렬한다. 2. 단어의 길이가 길수록 앞으로 배치한다. 3. 알파벳 사전 순으로 앞에있는 단어일수록 앞에 배치한다. N과 K, N개의 단어가 주어졌을때,..
[백준 / BOJ] 8972 미친 아두이노 문제 출처 : https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 종수는 R*C의 그리드에서 아두이노를 움직이는 게임을 진행한다. 이 게임에는, 종수의 아두이노와 미친 아두이노가 있으며, 미친아두이노는 항상 종수의 아두이노와 가장 가까워지는 방향으로 움직인다. 미친아두이노의 위치, 종수의 아두이노의 위치, 종수의 아두이노가 움직이는 방향이 주어졌을때, 그리드의 최종상태를 출력하는 문제다. (단, 종수의 아두이노가 미친아두이노를 만난다면 즉시 종료..

티스토리툴바