1043번: 거짓말지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게www.acmicpc.net 과정과장된 이야기를 들은 사람은 감염된다고 생각하면 쉬웠다.마치 토마토 문제처럼? 백준 7569 (BFS)7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100ssin-estella.tistory.com그래서 먼저 진실을 알고 있는 사람만 큐에 저장후, 모든 파티를 순회하면서 새롭게 진실을 알게된 사람은 큐에 저장하고..

15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 과정 이전 15663번과 유사한데 수열이 무조건 오름차순으로 구성되어야한다는 차이점이 있다. 그래서 같은 수열 내에 바로 이전 숫자와 비교해서 같거나 더 클 경우에만 수열에 추가했다. 다만, 이전 숫자를 비교하는 과정에서 index가 0일 경우 이전 숫자가 없어서 잘못된 숫자가 나온다. 따라서 인덱스를 0~M-1이 아닌 1~M 까지로 저하고, 이에 맞춰서 몇몇 코드를 수정했다. 코드 #include #include #include using namespace ..

15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 과정 주어진 숫자를 오름차순으로 정렬 후 (sort) 주어진 숫자들 중 M개를 뽑아서 수열을 만든다. (중복X) 다만, 이번에는 주어지는 숫자들 중 중복되는 숫자가 있다. : 그래서 같은 수열이 나올 수 있다는 것! 그래서 처음에는 if 문에 number[count] != sortNum[i]를 추가해서 이미 출력된 이전 수열의 같은 자리 숫자 number[count] vs 현재 집어넣으려는 숫자 sortNum[i]를 비교했다. 이 코드의 반례는 다음과 같다. 원..

15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 과정 이전에 풀었던 문제 2가지를 섞은 유형이다. 1부터 시작이 아닌 주어지는 숫자들을 오름차순으로 정리, 같은 수를 골라도 되지만 반드시 오름차순으로 수열을 구성할 것. 백준 15654 (DFS, 백트래킹) 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M ssin-estella.tistory...

15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 과정 [C++/백준문제] - 백준 15650, 15652 (DFS) 백준 15650, 15652 (DFS) 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하 ssin-estella.tistory.com 이거랑 비슷한 문제인데 1부터 시작이 아니다. : 때문에 오름차순으로 정렬을 해줘야한다. 본인은 포함하지..

15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 과정 처음 보자마자 다중 for문이 생각났다. 다중 for문이면 대부분 DFS로 풀 수 있던걸 생각해서 DFS로 접근 처음에는 감이 안잡혔는데, 다음 그림을 그리게 된다. 1~6까지 수를 기준으로 3개의 숫자를 가진 수..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 과정 처음에는 DP : 자신을 포함하는 물건들의 최대 가치 를 담는 용도였다. #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N = 0; // 물건의 수 int K = 0; // 최대 무게 int W = 0; // 물건의 무게 i..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 과정 대놓고 트리라고 하니까.. 그냥 DFS로 작성했다. 부모만 찾으면 되는 문제라 간단하지만;; vector선언과 메모리크기를 초기화하는 과정에서 vector와 array의 차이를 잘 모르고 있었던 것 같다. 나는 지금까지 왠만하면 vector의 크기를 MAX로 미리 고정하지 않고 resize를 통해 정해줬다. (그게 메모리적으로 이득이니까) 근데 이번 문제는 vector의 장점을 이용해서 하나의 index안에 여러값을 push_back 해야한다. 근데 이럴 경우, 선언 자체를 메모리값이 0인채로 해서 그런지 오류가 발생한다..

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 과정 x2-x1, y2-y1 범위에 들어있는 숫자를 for문으로 더할까 하다가 그럼 시간초과가 날 것 같아서 애초에 숫자를 받을 때, 같은 열!!!!! 기준으로 누적값을 벡터에 저장한 후, 범위를 받아서 최대좌표의 누적값 - 최소 좌표의 누적값 을 했다. 이 문제를 풀 때 가장 시간이 오래걸린 점은 바로 행렬을 개같이 못했다는 점이다. 행 = Row = x값 = 가로 열 = Column = y값 = 세로 코드 #inclu..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 과정 맨 처음 문제를 보고 너무 쉽다고 생각했다. 그냥 수열 받을 때 마다 최대값 저장해서 비교하면 되는거 아닌가? 해서 나온 코드.. #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N = 0; // 수열의 크기 ve..