[백준]/C++

https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net #문제 간단 정리 #문제 해결 방법 성원이의 현재 몸무게를 x, 기억하고 있는 몸무게를 y라고 할 때, 주어진 조건은 x^2 - y^2 = G입니다. 이 식은 (x + y)(x - y) = G로 변환할 수 있으며, 우리는 x와 y의 모든 가능한 쌍을 찾아야 합니다. 그러나 주어진 조건에 따라 x와 y는 모두 자연수여야 하며, x > y 조건을 만족해야 합니다 여기서 자연수임을 확인하는 방법은 구한 y^2 값을 ..

https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net #문제 해결 방법 이 문제를 해결하기 위한 로직은 '슬라이딩 윈도우' 기법을 사용합니다. 이 기법은 일정 범위의 데이터를 순차적으로 이동시키면서 연산을 수행하는 방법입니다. 구체적으로, 문제의 해결 로직은 다음과 같습니다: 초기화: maxVisitor: 최대 방문자 수를 저장하는 변수입니다. 이를 0으로 초기화합니다. nowVisitor: 현재 윈도우(즉, 연속된 X일)의 방문자 총합을 저..

#문제 간단 정리 dp 를 사용해서 풀어야한다 #문제 해결 방법 문제 상황 먼저, 문제 상황을 이해해야 합니다. 여기서는 가로로 2칸, 세로로 N칸인 우리가 있고, 사자들을 배치하는 문제입니다. 조건은 다음과 같습니다: 사자들은 가로나 세로로 붙어 있을 수 없습니다. 사자를 한 마리도 배치하지 않는 경우도 포함합니다. 동적 프로그래밍 이해하기 DP는 큰 문제를 작은 문제로 나누어 푸는 방법입니다. 이 문제에서는 'N번째 칸까지 사자를 어떻게 배치할 수 있는가'를 작은 문제로 삼습니다. 각 칸에 대해 다음과 같은 세 가지 경우를 생각해볼 수 있습니다: 사자를 배치하지 않는 경우. 사자를 첫 번째 칸에만 배치하는 경우. 사자를 두 번째 칸에만 배치하는 경우. DP 배열 설정 DP를 사용하기 위해 각 상태를 ..

https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net #문제 해결 방법 슬라이딩 윈도우를 사용하자 #전체 코드 #include #include using namespace std; int main() { int N, d, k, c; cin >> N >> d >> k >> c; vector sushi(N); vector sushiCount(d + 1, 0); for (int i = 0; i < N; i++)..

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net #문제 해결 방법 투 포인터를 사용하자 #전체 코드 #include #include using namespace std; int main() { int n; cin >> n; string s; cin >> s; int st = 0, en = 0; int maxLength = 0; int curType = 0; int alpha[26] = { 0, }; while (en < s.length()) { if (..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net #문제 간단 정리 위상정렬을 사용해 문제를 풀자. #전체 코드 #include #include #include #include using namespace std; int main() { int T; cin >> T; while (T--) { int N, K; cin >> N >> K; vector build_time(N + 1, 0); vector indegree(N + 1, 0); vec..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 Dynamic Programming (DP)을 사용하여 해결할 수 있는 문제입니다. 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)를 찾는 문제입니다. #발상 주어진 수열 A에서, 각 위치에서 그 위치를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 찾아보..

https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net #문제 간단 정리 dp 를 쓰자 주의할건 dp 배열의 초기값을 높게 설정해 줘야 한다 최소값을 고르는거기 때문에 0이 설정되어 있다면 최소값으로 0이 선택되기 때문이다. #전체 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector c..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net #전체 코드 #include #include #include using namespace std; vector tree[51]; int check[51]; int leaf = 0; int wither; int root; void findLeaf(int node ) { check[node] = true; if (node == wither) return; bool isLeaf = true; fo..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net #문제 간단 정리 문제 풀이 전략 문제의 목적은 주어진 규칙에 따라 연속된 집들을 서로 다른 색으로 칠하는 최소 비용을 찾는 것입니다. 이러한 유형의 문제는 동적 프로그래밍(dynamic programming, DP)을 사용하여 해결할 수 있습니다. 문제를 해결하는 전략은 다음과 같습니다: 먼저, 각 집을 칠할 때의 비용을 2차원 배열에 저장합니다. 그런 다음, 다른 색상 조..