https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 이 문제는 조합을 이용한 완전 탐색 문제이다. 조건에 따라 음식을 만들 수 있는 경우의 수는 {1}, {2}. {3}, {4}, {1,2}, {1,3}, {1,4}, ..., {1,2,3,4} 등이 존재한다. 따라서 입력으로 들어온 신맛과 쓴맛의 차이를 조합하여 최소 값을 구하면 해결할 수 있다. 최소 값을 구하는 과정은 다음과 같다. 입력은 신맛과 쓴맛이 존재하기 때문에 p..
분류 전체보기
https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 이 문제는 DFS를 통한 완전 탐색을 이용해 해결해야한다. 꽃은 십자가 모양으로 키워지며, 3개의 꽃은 서로 겹치면 안된다. 이는 DFS를 통해 탐색을 진행하고 꽃을 키울 수 있는지 확인한 후 키울 수 있다면 밭의 비용을 십자가 모양으로 산출하면 된다. 꽃은 테투리 범위에 키울 수 없으므로 테투리까지 탐색하지 않아도 된다. 따라서 반복을 1부터 N-1까지 진행하는 것이며, DFS를 위한 탐색 범..
https://www.acmicpc.net/problem/9079 9079번: 동전 게임 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 www.acmicpc.net 이 문제는 행, 열, 대각선을 뒤집는 2^8개의 경우의 수를 모두 확인하면 해결할 수 있다. 9x9 크기의 동전의 상태를 0과 1로 나타내기 위해 T는 0, H는 1으로 나타낸다. 주어진 보기 중 H T T H T T T H H 는 100 100 001이 되며 비트로 바꿀 때 거꾸로 읽어 변환하기 때문에 100 001 001인 393이 된다. 동전을 뒤집는 값은 { 000 000 111, 0..
https://www.acmicpc.net/problem/16937 16937번: 두 스티커 첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다. www.acmicpc.net 이 문제는 조합을 통한 완전 탐색을 이용하면 해결할 수 있다. 문제에서 두 개의 스티커만 이용하라고 되어 있어, 2 개의 스티커를 고르면 가로나 세로로 붙인 결과의 최대 값을 출력하면 된다. 입력된 스티커의 가로, 세로 값과 90도 회전할 수 있으면 회전한 가로, 세로 값을 배열에 삽입한다. 회전 가능한 스티커는 가로, 세로 값이 같지 않은 스티커만 가능하다. 또한 뒤집은 스티커와 뒤집지 않은 스티커를 고르지 않게 해야한다. 즉, 동일한 스티커를 고르..
https://www.acmicpc.net/problem/16508 16508번: 전공책 곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 www.acmicpc.net 이 문제는 조합을 이용한 완전 탐색을 이용해 해결해야한다. 선택한 책들의 알파벳 개수와 T의 알파벳 개수를 비교하여, 선택한 책들로 T를 만들 수 있다면 result를 갱신해 준다. 이때, result는 더 작은 값만 넣어준다. 선택한 책들로 T를 만들 수 있는지 확인하는 함수는 check 함수이며, alpha 배열에 들어있는 (입력한 문자열) 문자와 책들을 통해 얻은 문자(target) 배열을 비교..
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 이 문제는 투 포인터를 사용해서 회문인지 유사 회문인지 검사하면 해결할 수 있다. 문제에서 주어지는 회문 검사는 algorithm에 있는 reverse 함수를 통해서도 검사할 수 있다. reverse 함수에 의해 구할 수 있는 결과는 유사 회문은 검사할 수 없다. 따라서 회문인지 유사회문인지 그냥 문자열인지 한번에 판단하기 위해서 모든 검사를 투 포인터를 사용하는 것이 좋다. 회문인지는 0번째 인덱스(left)와 input.s..
https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 이 문제는 투 포인터를 사용해서 해결할 수 있다. 문제에서 주어지는 최대 K 번 삭제한 짝수로만 이루어진 연속한 부분 수열이라는 뜻은 홀수가 K번 이하 존재하는 연속한 부분 수열을 찾으라는 의미이다. 이러한 생각을 바탕으로 예제를 접근하면 아래와 같은 결과가 나온다. 1 2 3 4 5 6 7 8 이 주어지면 2 4 6 이 정답이 될 수 있다. 초기 start 포인터가 가리키는 0번째 인덱스가 홀수 인 경우 1 아닌경우 0으로 c..
https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 이 문제는 투 포인터를 사용해서 해결할 수 있다. 이 문제의 핵심은 구간 합을 반복문이 아닌 누적 합을 사용해서 해결해야한다는 것이 핵심이다. 구간 합을 반복문을 사용하면 O(N^2)이 되어 시간 초과가 발생한다. 따라서 값을 계속 해서 누적하고 합이 X보다 커지면 end 지점의 값을 빼고 end 포인터를 이동시킨다. 이러면 구간의 합을 계속해서 누적할 수 있다. #include using..
