이 시리즈는 백준 문제 풀이를 올릴 예정입니다.
10171 고양이문제
10828 스택
10845 큐
처음에 조합(Combination)을 이용한 재귀로 풀면 되겠다는 생각을 했습니다. 하지만, 시간 제한으로 다른 방법을 찾아야했습니다. Dynamic Programming을 이용해서 풀어보겠습니다. dpN을 N개와 M개의 사이트로 만들 수 있는 다리의 수라고 정의하겠습
기본 아이디어는 다솜(기호1번)의 득표수보다 다른 후보의 득표수가 크거나 같으면 매수해서 다솜의 득표수는 +1 하고 표를 뺏긴 후보의 득표수는 -1을 한다.문제에서 매수하는 사람 수의 최솟값을 구하라고 수정한 코드
문제만 읽으면 어려워 보일 수 있지만 길이가 64인 막대를 자르면, 32, 16, 8, 4, 2, 1로 나눠진다.(2^5, 2^4, 2^3,,,2의 제곱승)길이가 X인 막대는 위 길이의 막대들의 조합으로 만들 수 있다.이 말은, 2의 제곱승의 조합으로 X를 만들면 된다
이 문제는 문자열과 정렬을 이용해서 풀 수 있습니다. 코드
이 문제는 그래프와 DFS를 이용해서 풀었습니다.각 지점에서 인접한 지점은 총 8개입니다.(일반적으로)기본 아이디어는 각 지점에서 DFS를 해서 DFS를 호출한 지점의 높이보다 큰 높이가 있는 지점이 없으면 산봉우리입니다.(만약, 높이가 같은 지점이 있다면 DFS를 호
1자리 이친수 : 1 -> 1개2자리 이친수 : 10 -> 1개3자리 이친수 : 100, 101 -> 2개4자리 이친수 : 1000, 1010, 1001 -> 3개5자리 이친수 : 10000, 10100, 10101, 10010, 10001 -> 5개위 이친수들을 보면
기본아이디어는
입력받은 숫자가 1, 11, 111,,, 111----111 중 나누어떨어지는 수를 찾으면 됩니다. 처음에는 밑에 있는 코드처럼 풀었습니다.결과는 시간초과였다. 코드 하나를 추가해서 해결했습니다.예를 들어서 3을 입력받으면 답은 111입니다.11 10 + 1 = (3
풀이는 다시 올릴 예정입니다.int main() { string statement; cin >> statement;}