https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 dynamic programming 문제이다. dp에 상담 금액의 최대 값을 저장한다. 이때 상담 시간을 결정하면 일정 기간동안 다음 상담을 신청할 수 없다는 조건이 있기 때문에 현재 결정한 상담 시 금액과 지난 상담의 합과 dp에 저장된 현재 결정한 상담 시간과의 최대 값을 골라 dp에 저장해야한다. #include using namespace std; ..
Baekjoon Review
https://www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 이 문제는 누적합을 구하여 해결하는 문제이다. 이문제는 11660번과 동일한 알고리즘을 사용하면 된다. https://hanseongbugi2study.tistory.com/67 [Silver 1] 11660번 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ..
https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 이 문제는 T를 통해 S를 만들 수 있는지 확인하는 문제이다. 입력으로 S와 T가 들어온다면, S와 T가 같은지 확인인다. 만약 다르다면 문자열의 길이가 다르다면 A와 B를 붙일 수 없으므로 제귀를 멈춘다. 만약 T의 끝이 A인 경우 temp 변수에 T를 담고 A를 제거하고 다시 문자를 붙일 준비를 한다. 만약 T의 앞이 B인 경우 temp 변수에 T를 담..
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 이 문제는 조합을 이용한 완전 탐색 문제이다. 팀은 2개로 이루어져 있고, 팀의 최소 인원은 2명이다. 따라서 2명의 묶음이 만들어 졌을 때 팀원의 능력치를 더한 후 2개의 팀간의 능력치 차이의 절대 값을 구하면 된다. 팀 간의 묶음은 다음과 같다. 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 ..
https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 이 문제는 완전 탐색으로 오목을 구현하는 문제이다. 오목은 가로, 세로, 좌 대각, 우 대각으로 만들 수 있다. 또한 문제에서 오목이 만들어 졌을 때 가장 왼쪽의 인덱스를 출력해야한다. 문제의 특성을 생각해 봤을 때 한쪽 방향으로만 검사하면 된다는 것을 알 수 있다. 즉, 반드시 가장 왼쪽의 인덱스를 출력해야 한다는 것은 왼쪽으로만 검사하면 된다는 의미이다. 그러면 가로 검사, 대각 검사도 왼쪽으..
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..
