개발지식 먹는 하마 님의 블로그

[ 풀이 ]서로 다른 길이의 N개의 랜선을 잘랐을 때, 동일한 길이의 랜선이 K개 이상이어야 한다.-> 동일한 길이의 랜선 개수 = x cm로 각 랜선을 나눴을 때의 몫의 합 최대 랜선의 길이를 구하자-> K를 만족하는 길이를 찾아도 우측 탐색을 지속함랜선의 길이는 2^31-1보다 작거나 같은 자연수이다. -> 정수가 매우 큰 단위까지 사용된다.-> long long 타입 사용[ 코드 ]#include #include #include using namespace std;typedef long long ll;int n = 10000;vector lens;int calcNumofLen(int length) { //동일한 길이의 랜선 개수 계산 ll result = 0; for (auto l : lens) {..

[ 풀이 ]lower_bound와 upper_bound를 이용했다.(탐색된 값이 초과되는 지점 - 탐색값이 시작되는 지점)으로 중복된 개수를 구하였다.[ 코드 ]#include #include #include using namespace std;int n = 500000;int m = 500000;vector cards;int checkCardsNum(int num) { //중복되는 카드 개수 세기 auto minAdd = lower_bound(cards.begin(), cards.end(), num); auto maxAdd = upper_bound(cards.begin(), cards.end(), num); int result = maxAdd - minAdd; return result;}int main..

[ 풀이 ]정수의 범위가 너무 커서 배열을 통해서 이전에 찾은 값을 저장해 두는 것은 안 될 것 같았다.대신 탐색 경우를 조금이라도 줄이기 위해서 2가지를 조건문으로 확인했다.1. 찾고자 하는 값이 저장된 정수 범위 내에 있는가.2. 정수 범위의 최솟값 또는 최댓값과 동일한가.찾고자 하는 값이 저장된 정수 범위 내에 있는 경우 이분 탐색을 진행한다.값이 존재하면 1을 출력하고, 존재하지 않으면 bool 변수를 통해 판별하여 0을 출력하도록 했다.(이분탐색을 별도의 함수로 정의해서 반환값으로 판별해도 좋을 것 같다.)[ 어려웠던 점 ]출력 초과 오류가 발생해서 이를 해결하는 데 시간이 조금 걸렸다.탐색이 되지 않았을 때를 고려하지 않아서 발생한 문제였다.isExist 변수로 이를 처리하니 오류를 해결할 수..

https://www.acmicpc.net/problem/11053> 제한조건더보기시간제한 : 1초메모리 제한 : 256MB> 문제더보기수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.> 입력더보기첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)> 출력더보기첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.> 풀이1. 이분 탐색 법의 lower_bound를 사용한다.2..

https://www.acmicpc.net/problem/2805> 제한조건더보기시간제한 : 1초메모리 제한 : 256MB> 문제더보기상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는..

분할 정복 기초 문제> 제한조건더보기시간제한 : 1초메모리 제한 : 128 MB> 문제더보기아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞..

https://www.acmicpc.net/problem/11729> 제한 조건더보기시간제한 : 1초메모리 제한 : 256 MB> 문제더보기세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.아래 그림은 원판이 5개인 경우의 예시이다.> 입력더보기첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다> 출력..

https://www.acmicpc.net/problem/7576> 제한 조건시간제한 : 1초메모리 제한 : 256 MB> 문제더보기철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 ..

https://www.acmicpc.net/problem/2606> 제한 조건시간제한 : 1초메모리 제한 : 128 MB> 문제더보기신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨..