개발노동자

문제 상근이는 근처 피자 가게에서 매일 저녁으로 피자를 배달해 먹는다. 주머니 사정이 얇아진 상근이는 이번 달부터 "최고의 피자"를 구매하려고 한다. 최고의 피자란\, 피자 가게에서 주문할 수 있는 피자 중 1원당 열량이 가장 높은 피자를 말한다. 최고의 피자는 여러 종류가 있을 수도 있다. 이 피자 가게는 토핑 N개에서 여러 종류를 선택해서 주문할 수 있다. 같은 종류의 토핑을 2개 이상 선택할 수는 없다, 또 토핑을 전혀 선택하지 않을 수도 있다. 선택한 토핑은 도우 위에 올라간다. 도우의 가격은 A원이고, 토핑의 가격은 모두 B원이다. 피자의 가격은 도우와 토핑의 가격의 합계가 된다. 증 토핑을 k종류 선택했다면 피자의 가격은 A+B*k원이 된다. 피자의 열량은 도우와 토핑의 열량의 합이다. 도우의..

문제 경래는 닭을 기르는데 올 겨울 달걍 풍년으로 함박 웃음을 짓고 있다. 그리고 이 달걀을 영양란을 둔갑하여 옥션에 판매하려한다. 경래는 총 N개의 달걀이 있고, 그의 잠재적은 고객은 총 M명이다. 그리고 i번쨰 고객은 각자 달걀 하나를 P 가격 이하로 살 수 있다고 밝혔다. 경래는 영양란이라 속인 죄책감에 한 고객에게 두 개 이상의 달걀은 팔지 않기로 하였다. 하지만 위의 규칙 하에 수익은 최대로 올리고 싶기에 얼마로 팔지 고민하고 있다. 즉 A가격에 달걀을 판단고 하면 P가 A가격보다 크거나 같은 모든 고객은 달걀을 산다는 뜻이다. (물론 달걀 총 수량을 초과하여 팔 수는 없다.) 문제는 이러한 경래를 도와 최대 수익을 올릴 수 있는 달걀의 가장 낮은 가격을 책정하는 것이다. 입력 첫째 줄에 정수 ..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 문제 항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다. 파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 센다. 항승이는 길이가 L인 테이프를 무한개 가지고 있다. 항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우..

문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번의 컴퓨터는 1번 컴퓨터와 네트워크 상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. ㅇ어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의..

문제 오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다 정점 번호는 1번부터 N 번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색을 노드를 방문할 경우 노드의 방문 순서를 출력하자 인접 정점은 오름차순으로 방문한다. 풀이 1. Queue를 생성한다. 2. Queue에 시작 노드 번호를 add 한다. 3. visited 배열에도 시작노드를 방문처리한다. 4. result배열을 만든다. --> 인덱스가 각 노드이고 순서를 지정한다. (3번 인덱스에 4가 들어가면 3번 노드는 4번째로 방문한다는 뜻임) 5..

문제 오늘도 서준이는 너비 우선 탐색 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자 N개의 정점과 M개의 간선으로 구성된 무방향 그래프가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자 인접 정점은 내림차순으로 방문한다. 풀이 방법 -> 1번 인접 리스트로 주어진 간선들을 받아 생성 -> 2번 인접 리스트를 모두 내림차순으로 정렬한다. -> 3번 BFS 방식 그대로 적용하여 탐색을 시작한다. -> Queue에 시작점 담고 while에서 poll하고 poll한 값 for문 돌리는식으로 진행 -> 4번 진행 하기 전에 count 배열을 만들어 순서를 ..

문제 N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비우선 탐색으로 만들어 지는 트리를 너비우선 탐색 트리라고 하자. 너비 우선 탐색 트리에 있는 모든 노드의 깊이(depth)를 출력하자. 시작 정점 R의 깊이는 0이고 방문 되지 않은 노드의 깊이는 01로 출력하자 문제에서 트리라는 표현을 이해 못해 계속 틀리고 억지로 맞췄는데 출력초과로 계속 틀렸다.... 결국 이 문제는 자식노드를 다 같은 depth로 보고 풀어야 한다. 그렇기 때문에 일반적으로 bfs를 표현할 때 시작 점부터 큐에 담고 하나씩 뽑으면서 while(!q.isEmpty())를 돌리며 큐를 하나씩 뽑아 f..

문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S가 주어진다. (1 ≤ S ≤ 4,294,967,295) https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 일단 S의 범위가 크므로 long을 받아서 해야한다. 처음에 int로 했었는데 시간초과... 문제 풀이 - 1부터 주어진 숫자까지 for루프를 돌면서 num에 루프 인덱스를 계속 더해 나간다. 그러면 num은 점점 값이 커질 것이고 결국 주어진 값을 넘어갈 것이다. 주어진 값을 넘긴 순간 break를 걸어야 한다. - 여기에 문제 조건은..

문제 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 이 부분이 잘 이해가 안 갔는데 이 부분을 코드로 보면 사이클을 이런식으로 만들 수 있다. 이렇게 만들어진 사이클을 구해 출력하는데 여기서 테스트 케이스 숫자도 주어진다. 1. arr을 만들어 주어진 숫자를 배열에 넣는다. 2. visited 배열을 만들어 방문처리를 하는데(여기서 visited 인덱스가 그래프를 나타냄..

문제 총 N개의 시험장이 있고, 각가의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 A명이다. 감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관으,ㄴ 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다. 각각의 시험장에서 총감독관은 오직 1명만 있어야 하고,, 부감독관은 여러 명 있어도 된다. 각 시험장마다 응시생들을 모두 감시해야 한다. 이때 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오 풀이 처음 while문으로 전부 순회하며 푸니 당연하게 시간초과.. 순서 1. 총감독은 한명은 무조건 있어야 하고 그 이상은 존재할 수 없다. 결국 주어진 교실만큼 총감독이 들어감 2. 학생이 100명일 경우 총감..