Development Project

문제 링크 : https://www.acmicpc.net/problem/1099 1099번: 알 수 없는 문장 첫째 줄에 문장이 주어진다. 문장의 길이는 최대 50이다. 둘째 줄에 단어의 개수 N이 주어지며, N은 50보다 작거나 같은 자연수이다. 셋째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최 www.acmicpc.net 소요 시간 : 3일정도 고민하고 풀었음. 알 수 없는 문장 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 1880 574 388 32.119% 문제 형택이와 그의 친구들은 자꾸 다른 사람들이 대화를 엿듣는 것이 짜증났다. 따라서, 새로운 언어를 만들었다. 이 언어에는 단어가 N개 있다. 그리고 이 언어의 문장은 단어를 공백없이 붙여쓴 것이다..

문제 링크 : https://www.acmicpc.net/problem/1501 1501번: 영어 읽기 첫째 줄에 사전에 있는 단어들의 개수 N(0 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄에 하나씩, 영어 사전에 있는 단어들이 주어진다. 각 단어의 길이는 100자를 넘지 않는다. 다음 줄에 www.acmicpc.net 소요 시간 : 2시간 영어 읽기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 1425 273 186 18.826% 문제 혹시 인터넷을 하다가, 다음과 같은 식의 문장을 본 적이 있는가? It is itnersetnig taht pepole can raed smoe grabeld wrods. 원래의 문장은 'It is interesting..

문제 링크 : https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 소요 시간 : 1시간 반 AC 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 93352 20647 14575 19.860% 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는..

문제 링크 : https://www.acmicpc.net/problem/1069 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 소요 시간 : 3시간.. 집으로 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 3987 1032 792 27.123% 문제 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법은 점프하는 것이다...

문제 링크 : https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 소요 시간 : 1시간 50분 가장 큰 정사각형 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 32851 9763 7039 29.355% 문제 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 입력 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000..

문제 링크 : https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 소요 시간 : 2시간 알파벳 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 82419 26408 16163 29.046% 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로..

문제 링크 : https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 소요 시간 : 2시간 반 컵라면 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 9247 2741 2059 31.122% 문제 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다. 문제 번호데드라인컵라면 수 1 2 3 4 5 ..

문제 링크 : https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 소요 시간 : 거의 4시간? 정도.. 로봇 조종하기 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 12267 4279 2943 33.855% 문제 NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다. 지형의 고저차의..

문제 링크 : https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 소요 시간 : 1시간 팰린드롬? 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 (하단 참고) 256 MB 41063 11640 7930 29.352% 문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드..

문제 링크 : https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 소요 시간 : 2시간 반 경사로 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 22652 12421 8935 55.753% 문제 크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다. 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 다음과 같은 N=6..

문제 링크 : https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 소요 시간 : 2시간 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 256MB 문제 원숭이가 점프 할 수 있는 횟수K(0≤K≤30), 지도의 가로W, 세로 H(1≤W,H≤200) 원숭이가 한번에 상하좌우 한칸씩 갈 수 있는데, K번만큼 체스의 나이트처럼 움직일 수 있을 때 최소 몇번의 이동으로 도착지(지도의 가장 우측하단)까지 갈 수 있는지 출력하는 문제 이해 ..

문제 링크 : https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 소요 시간 : 2시간 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 512MB 문제 N x M의 지도(1≤N,M≤50)에 숫자나 구멍(H)가 기록되어 있다. 지도의 왼쪽 상단으로부터 출발하여 해당 포지션에 기록된 숫자만큼 상/하/좌/우로 이동이 가능한데, 맵밖으로 빠져나가거나 구멍에 도착하지 않는 한 무한히 이동이 가능하다. 이때, 최대로 이동할 수 있는 횟수를 구하는 문제이다..

문제 링크 : https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 소요 시간 : 2시간 반 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 128MB 문제 W x H의 지도(1≤W,H≤100) 지도에 출발점 및 도착점(C), 벽(*), 빈방(.)이 있을때 C를 연결하기위한 최소 거울의 수를 출력하는 문제 거울은 /과 \모양이 있으며, 90도씩 방향을 회전 시킬 수 있다. 이해 문제이해는 어렵지 않았고, 완탐을 통해 전체 탐색하거나, 규..

문제 링크 : https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 소요시간 : 자바 파이썬 둘다 코딩하는 시간 포함 15분정도. 행복한 문제~ 이번 문제는 솔브닥 클래스를 올리고싶어서 풀게된 문제로, 최소힙을 구현할 수 있는지에 관한 문제이다! 우선 힙을 어떻게 구현해야하는지 살펴보자! 자바의 경우 PriorityQueue를 이용해 최소힙과 최대힙 둘다 구현 가능하다 만약 사용자 정의 Class를 큐로 쓰고싶다면, Compara..

문제 링크 : https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소요 시간 : 1시간 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 1024MB 문제 자연수 N(1≤N≤4,000,000) N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제 이해 문제이해도 어렵지 않고, 소수라는 말만 봐도 에라토스테네스의 체를 이용하는게 최선이므로, 바로 구현방법이 떠올랐다. 문제를 익숙한 용어로 재정의와 추상화 문제이해가 어렵지 않아서 생략하겠다. 문제를 어떻게 해결할 것인가 1st 접근 - 에라토스테네스의 체와 투포인터 배열) 소수를 에라토스테네스의 체를 ..

문제 링크 : https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 소요 시간 : 2시간 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 512MB 문제 NxN의 지도(2≤N≤20), M명의 승객(1≤M≤N^2), 초기연료(1≤N≤500,000) 지도의 크기및 상태가 주어지고 택시의 출발점, 각 승객의 출발지 도착지가 주어졌을때, 주어진 연료를 사용하여 모든승객을 도착지로 데려다주고 남은 연료의 최댓값을 구..

문제 링크 : https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 소요 시간 : 3시간 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 192MB 문제 N개의 꽃(1≤N≤100,000) 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어있어야 하고, 가능한 정원에 심는 꽃들의 수를 가능한 적게 해야한다. 이해 조건대로 수행하면 되는데, 이제 어떻게 접근하여 최적화 할지 생각해야하는 문제이다. 문제를 익숙한 용어로 ..

문제 링크 : https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 소요 시간 : 50분 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 128MB 문제 11명의 선수가 11개의 포지션에 배치될때, 모두의 능력을 잘 발휘하여 모든 선수의 총 능력치 합의 최대를 출력하는 문제 이해 문제가 간단해서 이해가 어렵진 않았다. 문제를 익숙한 용어로 재정의와 추상화 이해가 어렵지 않아서 생략했다. 문제를 어떻게 해결할 것인가 백트래킹을 사용해야 할것같아서 조건을 따지기 위해 그려보았다..

문제 링크 : https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 소요 시간 : 3시간.. 문제를 읽고 이해하기 제한 시간 : 1초 메모리 : 512MB 문제 블록을 놓을 횟수(1≤N≤10,000), t개의 블럭 종류(1≤t≤3) 좌표 x(0≤x≤3), y(0≤y≤3) 빨간색 영역 안에서 3가지 종류의 블럭중 하나를 놓으면, 각각 초록색, 파란색 영역으로 떨어진다. 빨간영역에 블럭을 놔둔 좌표를 기준으로 초록영역은 같은 열에 맞게 떨어지..

문제 링크 : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 소요 시간 : 1시간 반 문제를 읽고 이해하기 제한 시간 : 2초 메모리 : 256MB 문제 N개의 집(2≤N≤100,000), M개의 길 수(1≤M≤1,000,000), 길 유지비(1≤C≤1,000) 두개의 마을로 분할할때, 나머지 길의 유지비의 최솟값을 출력하는 문제 이해 N개의 집(노드), M개의 길 수(간선), C의 유지비(가중치)이므로,..