1일1알

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 숫자들의 순서가 다르더라도 같은 숫자로 취급하기 때문에 오름차순으로 정렬된 숫자들만 고려하였다. 2차원 dp테이블 dp[n+1][21]을 만들었다. n+1은 입력받은 숫자가 n이기 때문에 n까지 저장할 수 있고, 21은 2^20이 약 1000000이기 때문에 저렇게 설정하였다. dp[r][c]가 나타내는 값은 r의 숫자에서 2^c가 가장 마지막으로 오는 숫자들의 합의 개수라고 설정하였다. 예를 들어 4의 경우, dp[4][0]은 2^0은 1이기 때문에 1이 마지막으로 오는 경우는 1 + 1 + 1 + 1 하나만 존재하고, dp[4][1]은 2^1은 2이기 때문에 2가 마지막으로 오는 경우는 1 + 1 + 2 , 2 + 2 이렇게 두 개가 존재한다. dp[..

리프 노드에 있는 말을 한 칸씩 올려서 루트 노드에 말이 도착하면 말이 사라지고, 모든 말이 사라짐과 동시에 차례가 끝난 사람이 이기는 게임이다. 생각을 조금 해보면 자기 차례때 어느 말을 선택하든 결과는 달라지지 않고, 단지 먼저 누가 시작했는지에 따라 승패가 정해지는 홀짝 게임 같은 게임이다. 결국 루트 노드에서 리프 노드까지의 모든 높이의 합에 따라 승패가 결정된다. dfs를 통해서 루트 노드에서 모든 리프 노드까지의 합을 구하고, 그 합이 홀수라면 성원이의 승리고, 짝수라면 성원이의 패배이다. 리프 노드와 연결된 노드는 무조건 하나이기 때문에 노드와 연결된 노드가 1개이고, 그 노드가 1이 아닐 때 (1은 루트노드라고 문제에 적혀있음) 를 dfs의 종료 조건으로 설정하였다. #include #in..

괄호 관련 문제가 나오면 거의 대부분은 스택 자료구조로 푼다고 생각하면 된다. 우선 문자열에 있는 문자들을 스택에 차례로 넣기 시작한다. 차례로 넣다가 스택의 top이 '{'이고 다음으로 넣을 문자가 '}'라면 안정적인 문자열이기 때문에 pop을 해주고 문자를 넣지 않고 넘어간다. 이런 방식으로 스택을 다 채운 뒤 위에서 2개씩 빼가면서 만약 2개가 '{', '{' 이거나 '}', '}'이면 하나만 뒤집으면 안정적인 문자열이기 때문에 cnt를 1 증가시킨다. 만약 2개가 '}', '{' 라면 둘 다 뒤집어야 안정적인 문자열이기 때문에 cnt를 2 증가시킨다. 이런 방법으로 스택이 빌 때까지 반복하면 답을 구할 수 있다. #include #include #include #include #include #i..

dp테이블을 이용해서 bottom-up 방식으로 해결할 수 있는 문제이다. 주의해야 할 점은 문제의 조건에서 비용의 제곱이 1000000보다 작다고 했기 때문에 음수가 비용으로 들어올 수도 있다는 점이다. 그렇기 때문에 들어오는 모든 경우들을 확인해주어야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; int cn..

맨 앞의 전구부터 순차적으로 만약 자기보다 앞에 있는 전구가 목표로 하는 상태와 같으면 누르지 않고 다음 전구로 넘어가고, 만약 다르다면 스위치를 눌러서 상태를 같게 만들어준 뒤 다음 전구로 넘어가는 방식으로 문제를 해결하였다. 여기서 주의해야할 점은 맨 앞의 전구는 자기보다 앞에 있는 전구가 없어서 비교가 불가능하기 때문에 맨 앞에 있는 전구를 눌렀을 때와 안눌렀을 때 이 두 경우를 모두 조사해야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; st..