🔗 문제 1931번: 회의실 배정 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 🖍 풀이 ✔️ 최적의 해를 구하는 방법 회의가 끝나는 시각으로 정렬한 후, 다음 회의 시작 시각보다 같거나 큰 회의를 잡는다. 회의가 언제 시작했던 빨리 끝내야 뒤에 시간이 많다는걸 생각해내면 된다. 시작 시각으로 정렬한 후 가능한 회의 개수는 3개 (오답) 종료 시각으로 정렬한 후 가능한 회의 개수는 4개 (정답) 시작 시각과 끝나는 시각을 std::pair로 저장했다. 종료 시각이 같다면 시작 시각이 빠른 걸로 선택할 수 있도록 정렬하기 위해 비교 함수를 커스텀해줘야 한다. bool compare(const std::pair& a, cons..

🔗 문제 https://www.acmicpc.net/problem/1449 🖍 풀이 HTML 삽입 미리보기할 수 없는 소스 [i번째 구멍 ~ 최대 j 구멍까지 거리] + [여유 거리 (1)]이 테이프 길이를 초과한다면? 그 바로 직전까지 i ~ j-1 는 한 테이프로 막을 수 있다. 먼저 입력이 오름차순이 아닐 수 있기에 구멍난 위치들을 정렬한다. #include ... std::sort(pipe, pipe+N); 그 후에 생각했던 가설을 코드로 옮겼다. for(int i=0; i= L)문으로 변경 💾 소스 #include #include #define MAX 10001 int main() { int N, L; int tape = 0; int pipe[MAX]; //input std::cin >> N >..

🔗 문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 🖍 풀이 뭔 소리인가 이해하는데 3분 더 걸린 문제 10, 15 로프를 예를 들자면 10 줄은 10 중량을 15 중량을 15 중량을 감당할 수 있다. 10과 15. 두 줄을 쓴다고 25 중량은 불가하다. 왜냐하면 10줄은 10까지 밖에 견딜 수 없기 때문이다. 그래서 두 줄을 모두 사용한다면 [가장 작은 10줄*사용줄 수] 값인 20이 정답이다. 💾 소스 #include #inc..

🔗문제 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 🖍풀이 메모리초과와 시간초과를 많이 봤다. 같은 로직으로 파이썬으로 제출했더니 맞았습니다 라서 더 힘들었다. (내 로직이 잘못되지 않았다는 믿음 → 로직 변경할 생각 x) 자릿수가 길어질 때 std::stoi나 std::to_string이 느린건가 싶어 별 짓 다 해봤다. 그래서 변환 없이 std::string끼리 비교하게 바꿨다. (비교대상이 둘 다 숫자라 오류는 안 났음) 첫번째 자리수가 0 일 때 스왑한 후 확인하는게 원인일까 싶어 스왑 전에 첫번째 자리..

memset() https://en.cppreference.com/w/cpp/string/byte/memset std::memset - cppreference.com Copies the value static_cast (ch) into each of the first count characters of the object pointed to by dest. If the object is a potentially-overlapping subobject or is not TriviallyCopyable (e.g., scalar, C-compatible struct, or an array of trivially copyab en.cppreference.com - 메모리 변화가 있는건 fill() 권유 하고 있..

🔗문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 🖍풀이 std::queue water; std::queue S; std::pair D; // 비버의 소굴은 이동하지 않는다. 입력을 받으면서 필요한 좌표들을 미리 저장한다. 필요한 좌표를 찾기 위해 이차원 함수를 탐색하고 싶지 않기 때문이다. 이동이 필요한 물과 도치를 BFS 탐색을 위해 queue에 저장한다. void BFS(std::queue& q, const bool isWater, bool& f..

🔗문제 16397번: 탈출 16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 www.acmicpc.net 🖍풀이 문제의 조건들만 잘 유의하면 바로 풀 수 있다. 어떤 경로를 통해서 값이 나왔는지 알고 싶어서 구조체를 이용해 풀었다. struct pair { public: std::string str; int num; pair(int _num, std::string _str) :num(_num), str(_str){}; }; str: 경로 num: 번호 BFS를 이용해 풀었기 때문에 G..

🔗문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 🖍풀이 내 기준 너무 너무 어려웠다. 결국 풀다가 검색의 힘을 빌렸고 참고하기 좋은 글을 첨부한다. 🔗 글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★ 글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★ 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net MAX 1,000인데 실수로 10,000으로 설정해서 틀렸..

🔗문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 🖍풀이 불 좌표, 상근이 좌표를 저장할 두 개의 queue를 생성하고 입력 받을 때 push해준다. std::queue fire; std::queue me; 재방문 방지 배열도 만들어 주었다. int visited[MAX][MAX]; 가장 중요한 BFS 탐색 방법 불 이동이랑 상근이 이동의 탐색에 겹치는 코드가 많아서 함수로 해결했다. void BFS(std::queue& q, const bool is..

> 연산자 (Shift) 비트를 n 만큼 왼쪽 혹은 오른쪽으로 이동시킨다. int n1 = 9; // (2진수 배열로 나열하면) 01001 int n2 = 11; // (2진수 배열로 나열하면) 01011 int n3 = n1 2 = 00010 = 2; int n3 = 28 > 2 = 00111 = 7; + 이때, shift 연산자는 곱셈, 나눗셈과 관련이 있다. 왼쪽으로 1칸 이동할때마다 정수의 값은 2배 로 커지고 (곱셈과 관련) 오른쪽으로 1칸 이동할때마다 정수의 값은 1/2배 가 된다. (나눗셈과 관련) 예제로 4/2 = 4>>1 과 동일한데, CPU 입장에서는 곱셈,나눗셈보다 비트 연산이 부담이 적어 성능 향상에도 도움이 된다. [출처] [c++] 비트 연산|작성자 YEON