본문 바로가기

분류 전체보기

 (265)
백준1449 - 수리공 항승 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 그리디의 기초인 문제라고 하는데 나는 되게 오래걸렸다. 그리디는 아이디어 문제인 경우가 많다. 여기서는 수직선의 원리를 이용하여 풀었다. 구멍사이의 간격은 테이프의 길이 - 1을 한 것으로 비교한다. 이유는 테이프의 시작과 끝을 0.5로 준다. 구멍사이의 간격보다 테이프의 길이가 짧으면 테이프의 갯수를 한 개씩 증가시킨다. 테이프를 붙이는 곳(min)은 구멍사이의..
백준5622 - 다이얼 https://www.acmicpc.net/problem/5622 5622번: 다이얼 문제 상근이의 할머니는 아래 그림과 같이 오래된 다이얼 전화기를 사용한다. 전화를 걸고 싶은 번호가 있다면, 숫자를 하나를 누른 다음에 금속 핀이 있는 곳 까지 시계방향으로 돌려야 한다. 숫자를 하나 누르면 다이얼이 처음 위치로 돌아가고, 다음 숫자를 누르려면 다이얼을 처음 위치에서 다시 돌려야 한다. 숫자 1을 걸려면 총 2초가 필요하다. 1보다 큰 수를 거는데 걸리는 시간은 이보다 더 걸리며, 한 칸 옆에 있는 숫자를 걸기 위해선 1초씩 더 걸린다. www.acmicpc.net 문제에서 주어진 상황은 문자열로 되어있는 번호를 해석하는 것이다. 각 번호마다 해당 문자가 써있고 1번 다이얼을 누르는데 걸린 시간은 2초가..
백준3986 - 좋은단어 https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 문제 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다. 평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 www.acmicpc.net 스택을 활용하여 푸는 문제이다. 문자를 한 개씩 스택에 넣고 top에서 같은 문자를 만나면 빼주는 형식으로 구현하였다. 좋은 단어의 경..
백준2870 - 수학숙제 https://www.acmicpc.net/problem/2870 2870번: 수학숙제 문제 상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다. 선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다. 글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 www.acmicpc.net 생각보다 조건이 까다로웠던 문제다. 파이썬으로 처리하면 간단했을 것 같다. 맨앞에 0처리를 해줘야 하였고 0으로만 이루어진 문자열은 0을..
백준17213 - 과일서리 https://www.acmicpc.net/problem/17213 17213번: 과일 서리 민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. 지환이는 완벽한 범죄를 위하여 처음 생각한 개수 만큼만 훔치려고 한다. 이때 지환이가 훔칠 수 있는 경우의 수가 몇가지나 될 지 알아보자. 단, 모든 종류의 과일을 적어도 1개는 훔친다. www.acmicpc.net 수학적 요소를 중시하는 문제이다. 처음에는 브루트 포스를 사용하려 했지만 문제를 잘 읽어보니 중복조합을 사용하면 될 것 같았다. N개의 요소 중 M개를 중복하여 선택하는 문제이다. N개의 요소는 모두 적어도 1개를 뽑아..
백준11729 - 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 재귀 호출에서 가장 기초가 되는 문제이다. 탑이 세 개가 존재하는데 첫번째 탑에 n개의 판이 작은 원판에서 큰 원판까지 ..
백준1541 - 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. www.acmicpc.net 그리디 문제 중 쉬운 편에 속했다. 0~9사이의 숫자와 -와 +가 임의로 주어졌을 때 괄호를 이용하여 최솟값을 찾는 문제이다. 더하기를 더하기끼리 최대한 묶은 후 뺄셈을 해주면 되는 문제다. ​ 예시를 들어 설명을 하자면 다음과 같다. 1. a - b + c - d + e 인 경우 a - (b + c) - (d + e) = a - b..
백준2012 - 등수 매기기 https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 그리디 알고리즘으로 풀었다. 1등부터 n등까지 학생들을 배치해야 하는데 학생들의 불만을 최소화하여 줄을 세우는 문제다. 입력받은 수를 소팅한 후 1등부터 n등까지 차례대로 빼주어 절댓값을 취해 답에 더해주면 된다. #include #include #include #include using namespace std; int main() { int n; vector v; //등수를 입력받을 변수 long l..

티스토리툴바