본문 바로가기

소스코드

 (42)
[백준 / BOJ] 16137 견우와 직녀 문제 출처 : https://www.acmicpc.net/problem/16137 16137번: 견우와 직녀 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다. 7월 7일은 견우와 직녀가 오작교를 건너 www.acmicpc.net 견우와 직녀는 여러 섬과 절벽으로 이루어진 크기 N*N 지역에 살고있다. 견우는 0,0에, 직녀는 N,N에 살고있다. 까치들은 견우와 직녀를 만나게해주기위해서, 오작교를 만드는데, 오작교는 T주기마다 생성되며, 1분동안 유지된다. 견우는 오작교를 2번이상 연속적으로 건널수없으며, 추가적으로 임의의 절벽에 다리를 하나 생성해서 건널수있다. 단, 다리를 생성할때, 교차로에는 짓지못하..
[백준 / BOJ] 4577 소코반 문제 출처 : https://www.acmicpc.net/problem/4577 4577번: 소코반 소코반은 1982년에 일본에서 만들어진 게임으로, 일본어로 창고지기라는 뜻이다. 이 게임은 캐릭터를 이용해 창고 안에 있는 박스를 모두 목표점으로 옮기는 게임이다. 목표점의 수와 박스의 수 www.acmicpc.net "소코반"이라는 게임을 플레이하는 시뮬레이터를 만들어야한다. 행과 열 R,C가 주어지고, 소코반의 상태가 주어진다. . 빈공간 # 벽 + 비어있는 목표점 b 박스 B 목표점 위에 있는 박스 w 캐릭터 W 목표점 위에 있는 캐릭터 이후, 캐릭터의 이동방향이 주어진다. UDLR(각각 up, down, left, right) 이때, 소코반게임이 끝나거나 캐릭터 이동이 끝났을때의 보드 상태를 출력하..
[백준 / BOJ] 1240 노드사이의 거리 문제 출처 : https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net N개의 노드로 이루어진 트리가 주어지고, M개의 쿼리가 주어질때, 노드 사이의 거리를 구하는 프로그램을 만드는 문제다. 풀이 트리 + 완전탐색 문제다. N이 1000, M이 1000으로, 한번탐색할때마다 최대 1000번 반복한다고 가정했을때, 최악의경우, 1000*1000번 반복하므로 시간복잡도는 O(NM)이 된다. 트리구조를 만든다음에 A위치에서 시작했을때, B위치에 도달했을때의 거리를 구하면된다. 거리구하는 소스코드 priv..
[백준 / 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] 20922 겹치는 건 싫어 문제 출처 : https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net N개의 수가 있는 수열이 주어진다. 이 수열중 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 문제다. 풀이 투 포인터로 풀은 문제다. 최장 연속 부분 수열이기때문에, 답이 될수있는 수열은 모두 붙어있어야한다. 따라서, 투 포인터로 left,right값을 지정한 후에 탐색하면 2N시간만에 답을 구할 수 있다. 메인 소스코드 private int getLon..
[백준 / 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개의 단어가 주어졌을때,..

티스토리툴바