pinevienna blog

정수 A에 2를 곱하거나, 가장 오른쪽에 1을 추가하여 정수 B를 만들 수 있다 몇 번의 연산으로 만들 수 있는지 구하는 문제 A에서 B를 만들지말고 B에서 A를 만들어야 할 것 같다.. A에서 B로 가려면 복잡해진다 B에서 1을 떼거나, 반으로 나눠주면 A를 찾을 수 있다 뭔가에 2를 곱했을 때 홀수는 나올 수 없으므로 B가 1로 끝나면 1을 떼어주고 (B/=10) 그 외의 홀수가 나왔는데 A와 같지 않다면 -1을 출력한다 짝수일 경우엔 반으로 나눠주면 된다 (B/=2) A==B일 때 cnt를 출력하고 프로그램을 종료하면 끝 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include using n..

수열 A = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고 수열의 길이는 4가 된다. 수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제 만약 {10, 12, 11, 12, 13, 15, 16, 18, 30} 이렇게 입력받는다면 12를 빼고 {10, 11, 12, 13, 15, 16, 18, 30} 이 가장 긴 수열이다 이걸 어떻게 판단하느냐.. 증가하는 수열의 길이를 dp배열에 넣고, 계속 비교해가며 가장 긴 수열을 찾으면 된다 dp[i]에 1을 넣어두고, A[1]부터 A[i-1]번째 수까지 A[i]와 비교하는 아주 dp스러운 문제.. A[j](1 ≤ j < i) 번째 수가 A[i]보다 작..

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 위 조건을 준수하며 최대한 많이 마실 때 얼마나 마실 수 있는지 출력하는 문제 오랜만에 나온 내 그림ㅎ 화살표 기준에서 생각해보자!! 연속으로 마실 수 없으니 1. 별이 그려진 두 잔 마시기 2. 동그라미 표시된 세 잔 마시기 3. 체크 표시된 두 잔 마시기 이렇게 세 가지 경우가 나올 수 있다 이 중 max값을 dp배열에 저장해가며 for문 돌리면 된다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include using namespace s..

지원자들의 서류, 면접 순위가 각각 입력됐을 때 두 개의 순위가 다른 어떤 지원자보다 둘 다 낮은 지원자는 결코 채용하지 않는다고 한다 채용할 수 있는 신입사원의 최대 인원수를 구하는 문제 3 6 7 3 4 2 1 4 5 7 2 5 6 1 위와 같이 입력받았다면 1 4 2 5 3 6 4 2 5 7 6 1 7 3 이렇게 서류 기준 오름차순으로 정렬해준다 여기서 가장 위에 위치한 1 4가 첫 기준이 된다 서류 기준 오름차순이므로 서류 등수는 볼 것도 없이!! 언제나!! 기준보다 등수가 낮을 것이다 그러니까 면접 등수만 비교하면 된다 면접 등수는 반드시 현재 기준보다 높아야 한다.. 둘 다 낮으면 무조건 탈락이라고 했으니까 1 4 count & 기준 2 5 둘 다 기준보다 등수 낮음 3 6 둘 다 기준보다 등..

k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다 각 로프들이 버틸 수 있는 중량이 주어졌을 때 들어올릴 수 있는 최대 무게를 구하는 문제 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다 설명하기 편하게 버틸 수 있는 무기게 무거울 수록 로프가 굵다고 가정해보자 3개의 로프가 있다면 1. 가장 얇은 로프 * 3 2. 그 다음으로 얇은 로프 * 2 3. 가장 굵은 로프 셋 중 가장 큰 값이 세 개의 로프를 적절이 이용하여 들어올릴 수 있는 최대 무게가 된다 10과 15 로프가 있다면 각각 10키로씩 총 20키로를 드는게 이득이고 ( 10 * 2와 15 비교, 20이 큼 => 20 ) 50과 5 로프가..