Problem Solving/Baekjoon Online Judge
-
[백준] 1664 소수의 연속합Problem Solving/Baekjoon Online Judge 2020. 5. 19. 00:03
✔️ 문제 링크 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 www.acmicpc.net ✔️ 문제 이해 ◾ 연속된 소수의 합으로 나타낼 수 있는 자연수 N이 주어진다. ◾ 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해야한다. ◾ 연속된 소수란 다음을 말한다. 2, 3, 5, 7, 11, 13 ◾ 다음은 연속된 소수가 아니다. 2, 3, 5, 7, 11, 17 (중간에 13..
-
[백준] 14465번 소가 길을 건너간 이유 5Problem Solving/Baekjoon Online Judge 2020. 5. 16. 23:05
✔️ 문제 링크 https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 문제 농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고�� www.acmicpc.net ✔️ 문제 이해 ◾ 일자형 길에 횡단보도 N개가 있다. (1 ≤ N ≤ 100,000) ◾ 뇌우로 인해 몇몇 횡단보도가 고장나있다. ◾ 연속한 K개의 신호등이 존재하도록 신호등을 수리하려고 한다. ◾ 연속한 K개의 신호등이 존재하도록 최소 몇 개의 신호등을 수리해야 하는지 출력한다. ✔️ 설계 ◾ 수리한 신호등의 개수를 이분 탐색을 통해 찾는다..
-
[백준] 10971 외판원 순회 2Problem Solving/Baekjoon Online Judge 2020. 5. 1. 15:17
✔️ 문제 링크 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net ✔️ 문제 이해 1. N개의 도시가 존재하고, 각 도시는 도로로 연결되어 있다. 각 도시간에 이동할때 비용을 지불해야한다. 2. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와..
-
[백준] 11723 집합Problem Solving/Baekjoon Online Judge 2020. 4. 29. 16:52
✔️ 문제 링크 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net ✔️ 문제 이해 1. 조건에 따른 구현을 하면된다. ✔️ 설계 1. check 배열을 이용해서 풀 수 있고, set으로도 풀 수 있다. 2. 하지만 비트마스크로 간단히 풀 수 있다. ✔️ 문제 회고 1. 비트마스크 연산에 대한 개념을 알고 있으면 매우 쉽게 풀 수 있다. 👨🏻💻 소스 코드 #include #include #include #include #include using namespace std; int m..
-
[백준] 14391 종이조각Problem Solving/Baekjoon Online Judge 2020. 4. 20. 22:03
✔️ 문제 링크 https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다. 영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 www.acmicpc.net ✔️ 문제 이해 1. 열 또는 행으로 조각을 나눴을 때, 각 조각에 써있는 숫자들의 최대 합을 구하는 문제이다. 2...
-
[백준] 1406 에디터Problem Solving/Baekjoon Online Judge 2020. 4. 16. 20:57
✔️ 문제 링크 https://www.acmicpc.net/problem/1406 1406번: 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 www.acmicpc.net ✔️ 문제 이해 1. 주어진 문자열에 대해 커서 관련 명령어를 수행한 결과를 출력한다. ✔️ 설계 1. 이 문제는 스택을 활..
-
[백준] 3980 선발명단Problem Solving/Baekjoon Online Judge 2020. 4. 16. 19:22
✔️ 문제 링크 https://www.acmicpc.net/problem/3980 3980번: 선발 명단 문제 챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다. 오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야 할지 아직 결정하지 못했다. 수석코치 마이크 펠란은 11명의 선수가 각각의 포지션에서의 능력을 0부터 100가지의 정수로 수치화 했다. 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다. 이때, 모든 선수의 포지션을 정하는 www.acmicpc.net ✔️ 문제 이해 1. 11명의 축구팀을 구성해야한다. 2. 11명의 선수의 각각의 포지션에 대한 능력치가 0부터 100..
-
[백준] 1806 부분합Problem Solving/Baekjoon Online Judge 2020. 4. 16. 15:56
✔️ 문제 링크 https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net ✔️ 문제 이해 1. 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 있다. 2. 이 수열에서 연속된 수들의 부분..