Algorithm/백준15 백준 1436 영화감독 숌 - C++ 접근 얼핏 보면 1666, 2666, 3666으로 증가폭이 1000으로 규칙성이 있어 보이지만 예외사항이 존재한다 6천번대로 진입하면 6660, 6661, 이런 식으로 규칙성에 예외사항이 생긴다. 약간 3,6,9 하면 30번대에 항상 박수를 치는 것과 비슷한 느낌이다. 그리고 N이 10,000까지다. 즉 N이 2일 때 1666인 걸 감안하면 N이 커지면 10666, 16660 뭐 이런 식의 시리즈도 생길 것이기 때문에 N이 커질수록 그에 맞는 규칙성을 파악하여 로직을 작성하는 것보다 최소한의 규칙(666을 포함)만 만족시키는 숫자를 지속적으로 찾게끔 로직을 만들어 주는 게 좋다. #include #include using namespace std; bool isThisEnd(int n){ string s.. 2020. 7. 21. 백준 1018 체스판 다시 칠하기 - C++ 접근 어떠한 M*N크기의 판이 있을 때 이 판을 8*8로 자를 수 있는 모든 경우의 수를 구한다. 각각의 8*8로 잘려진 판을 체스판으로 만들 때 다시 칠해야 하는 최소비용을 구해야 한다. 어떻게 구해야 할까? 우선, 체스판이 될 수 있는 조건은 맨 처음 칸 색깔이 검은색일 수도 있고 흰색일 수도 있다. 축소해서 생각해보자 체스판이 4*4라 했을때 WBWB BWBW BWBW WBWB WBWB BWBW BWBW WBWB 위와 같이 두가지가 나올 수 있다. 그렇다면 잘려진 판에서 맨 처음이 흰색으로 시작하는 체스판 그리고 검은색으로 시작하는 체스판 각각의 비용을 비교해 더 작은 값이 최소 값이 된다. #include #include using namespace std; string chess[50]; int.. 2020. 7. 20. 백준 2231 분해합 - C++ 접근 문제에서 보면 245는 256(245+2+4+5)의 생성자다 그런데 어떠한 N이 나왔을 때 N의 생성자를 알아내기 위한 규칙성을 찾기가 어렵다..어쩌면 없을지도 N이 2020일때 2020의 생성자는 2009인데 규칙성을 찾을 수가 없다. 따라서 브루트포스로 해결해야 하는 문제인데 숫자 1부터 높여가며 N의 생성자가 될 수 있는지 확인하는 과정을 거치면 O(N)이고 N은 백만보다 작으니 충분히 해볼만 하다. #include #include using namespace std; int makeSum(int num){ int result = num; string str = to_string(num); for(int i=0; i> N; for(int i=1; i 2020. 7. 20. 백준 7568 덩치 - C++ 접근 간단하게 한 명씩 자신을 제외한 모든 인원수와 비교하면서 등수 알아보기 입력을 2차원 배열에 넣고 배열을 순회하면서 배열 내에 있는 원소들과 비교한다. N명의 사람들은 각각 최대 N번씩 비교를 해야 하기 때문에 N 제곱 #include using namespace std; int main(){ int N; cin >> N; int arr[N][2]; for(int i=0; i> arr[i][0]; cin >> arr[i][1]; } for(int i=0; i 2020. 7. 20. 이전 1 2 3 4 다음
