https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 완전 탐색 문제로, n의 범위가 1000 밖에 되지 않으므로 3중 for문을 사용해서 해결했다! c++ #include using namespace std; int eureka[1001]; bool check(int n){ for(int i=1; i n; cout

https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 n이 100이라서 충분히 완전 탐색으로 풀 수 있을 것이라고 생각했다. (유형도 완탐이긴 했지만..ㅋ) 입력되는 벡터 배열인 wires는 간선을 나타내는 것이기 때문에 이 벡터 원소를 하나씩 빼서 2 그룹의 정점 개수 차이를 구하면 된다. tmp 벡터 배열을 하나 만들어서 erase함수로 간선을 하나 지우고 1부터 n 정점을 돌면서 방문하지 않은 정점이라면 BFS를 시작한다. BFS 내..

https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #include #include #include using namespace std; bool visit[9]; vector v; int ans = -1; int countDungeons(int tiredness, vector d){ int cnt = 0; for(int i=0; i= d[v[i]][0]){ cnt++; tiredness -= d[v[i]][1]; }else{ break; //ti..

https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 다른 사람들은 어떻게 저리 간단하고,, 멋진 방법으로 해결할 수 있을까.. 개쩐다.. 저는 한참 남았군요... 저는 약수를 사용해서 풀었습니다. 전체 카펫과 yellow 카펫의 약수를 구했습니다. 카펫은 직사각형으로 이루어지기 때문에 전체 카펫의 h, w는 전체 수의 약수들로 구성됩니다. 그래서 맞는 전체 카펫의 약수 짝꿍과 yellow 카펫의 약수 짝꿍을 완전 탐색으로 찾았습니다. 약수를 찾을 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 에라토스테네스의 체를 사용해서 소수를 빠르게 찾아볼까 했는데 그냥 하나씩 소수인지 체크해봐도 충분히 돌아간다. 자릿수 개수만큼 백트래킹을 사용해서 돌려서 수를 찾은 뒤에 소수인지 판별하고 set에 넣어서 중복을 제거해줬다. last는 마지막으로 사용한 원소가 무엇인지 저장해주는 것인데, 이를 통해서 "011"과 같은 수에서 BT를 통해 1이 두 개여서 발생할 수 있는 문제 → 01, 01 두 번 ..

https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 1로만 이루어진 n의 배수란, 1로만 이루어진 수 && n의 배수 1로만 이루어진 수는 1, 11, 111, 1111,.... 이런 식의 수다. 그러므로 1로만 이루어진 수를 쭉 만들면서 n의 배수인지 체크만 해주면 쉽게 풀 수 있는 문제. 1로만 이루어진 수 만들기 규칙! 1 => 0 * 10 + 1 11 => 1 * 10 + 1 111 => 11 * 10 + 1 1111 => 111 * 10 + 1 11111 => 1111 * 10 + 1 #includ..

https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 백트래킹으로 구현하면 되는데, 스타트팀이나 링크팀에 최소 한 명은 들어가야 한다. 그런데 1명만 들어가면 능력치를 구할 수 없다. 그러므로 2명부터~n-3명까지를 한 팀에 넣을 수 있다. for(int i=2; i

https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 이 문제는 삭제, 삽입을 계속해서 하면서 진행해야 한다. 처음에는 x 원소를 지웠다고 치고 배열 인덱스를 넘어가는 방식으로 할까 했는데 어떻게 해야할지 모르겠어서 그냥 vector의 erase, insert 함수를 사용했다. Backtracking을 통해서 1번째 원소와 마지막 원소를 제외한 나머지 원소를 골라서 차례대로 지우면서 양옆 에너지를 모아서 power에 더해주면 된다. #inclu..

https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 우선 수열을 정렬하고, 1개부터 수열의 개수만큼 백트래킹으로 부분 수열을 선택한다. 각 부분수열들의 합을 set에 넣어주고 자연수 1부터 set에 있는지 없는지 체크하고 없다면 바로 출력하고 끝낸다. set은 자동 정렬, 자동 중복 제거를 하기 때문에 사용하기 좋다. #include #include #include #include..