궤도

문제 풀이 0~9까지의 숫자를 1번씩만 쓸 수 있기 때문에 visited로 관리할 수 있다. 부등호에 따라 숫자를 넣으며 백트래킹하면 되는데 나중에 stoi를 쓰기 위해 string 변수에 답을 쌓아놓는다. 소스코드 #include #include #include #include using namespace std; vector sign; bool visited[10]; int k; long long min_num = 9876543211, max_num = 0; void backtracking(int pos, string str) { if (pos == k) { //부등호 다 쓰면 최대 최소 갱신 long long result = stol(str); min_num = min(min_num, result)..

문제 풀이 myunji.tistory.com/204 [백준] 14889번 : 스타트와 링크 문제 풀이 팀을 나누는게 가장 중요한 문제이다. 6명이 있을 때 3명을 고르고 나면 선택받은 3명은 스타트팀 선택받지 못한 3명은 링크팀에 넣어 계산하면 될 것이다. 근데, (1,2,3)번 사람을 고르 myunji.tistory.com 각 팀의 인원이 같아야했던 14889번과 달리 이 문제는 인원 수가 달라도 된다. 재귀함수로 풀어도 되지만 사실 이 문제는 비트마스크로도 풀 수 있다. 그래서 이번엔 비트마스크로 풀었다. 4명의 인원이 있다고 하자. 비트는 0 또는 1을 표시할 수 있으니 0은 링크팀, 1은 스타트팀이라고 하자. 0001 이라면 0번째 사람은 스타트팀, 1, 2, 3번째 사람은 링크팀인 것이다. 11..

문제 풀이 이 문제 덕분에 가끔은 정말 무식한 방법이 통할 때도 있단 것을 깨달았다. 원하는 채널로 가는 방법은 2가지가 있다. 1. +-버튼을 계속 누르기 2. 채널번호 입력후 +-버튼 누르기 일단 1번은 간단하다. 목표 채널과 현재 채널의 차이의 절댓값을 구하면 된다. 그리고 2번이 중요한데 난 가능한 모든 채널을 백트래킹으로 탐색해 최솟값을 갱신하려 했다. void backtracking(int pos, int digit) { if (digit == 0) //1 1 1 => 2 return; if (pos == digit) { int mul = 1, ch = 0; for (int i = 0; i < pos; i++) { int num = channel.back(); ch += (num * mul);..

문제 풀이 myunji.tistory.com/208 [백준] 1149번 : RGB거리 문제 풀이 이걸 이렇게 표현하는게 맞나? 싶지만 동적계획법 문제를 풀 때는 i번째가 ~라면 i-1번째는 뭐였을까? 라는 방법으로 접근하는 것이 좋다. 보통 문제를 풀 때 0번째가 이거라면 1번째는 myunji.tistory.com 이 문제의 응용 버전이다. 선형으로 배치됐던 집이 이젠 원형으로 배치된다. 고등학교 시절 원순열을 배울 때 선생님이 이런 말씀을 하셨다. "원순열은 시작점이 없어서 헷갈리니까 일단 한 놈을 죽여서 앉힌다고 생각해" 물론 죽인다 식의 표현은 격한 면이 있지만 덕분에 이렇게 몇년이 지난 지금도 잊지 않고 있다. 이 문제의 접근도 똑같이 하면 된다. 일단 첫번째 집의 색을 고정하고 집들을 색칠해 나..

문제 풀이 주어진 예제 입력이 하나인데다가 대충 생각해도 알 수 있는거라 좀 힘들었다. N의 입력이 무조건 짝수인 것만 계산했지 홀수인 경우에 0을 리턴해야 한다는 생각을 못해서 틀리기도 했고... dp배열엔 N/2를 저장할 것이다. 그니까 N=2면 dp[1]에 그 답이 있고, N=4면 dp[2]에 답이 있다. 아무튼 N=2일 때 타일을 채우는 방법은 다음과 같다. N=4라면 일단 처음 3x2를 N=2일 때처럼 채우고, 그 뒤는 dp[1]을 호출하면 된다. 이런식으로... 그럼 여기서 3*dp[1]이 된다. 근데 다른 방법으로도 타일을 채울 수 있다. 이런 모양이 2종류가 있다. 그럼 2*dp[0]을 하면 되는건가?? 여기서 N=6일때로 가면... 이런 것도 가능하고 이런 것도 가능하다. 그럼 dp[i]..

문제 풀이 dp는 점화식을 세우는게 제일 어렵다... 처음엔 2차원 dp배열을 선언해서 세로가 N(i)일 때 사자 j마리를 넣는다면...식으로 생각했지만, 나눠지는 경우의 수가 너무 많았다. dp인데 경우의 수가 일관적이지 않게 나눠진다면 뭔가 잘못하고 있단 뜻이니 바로 방향을 틀어야 한다... 그래서 i번째 줄에 집중하기로 했다. i번째 줄에서 가능한 경우는 3개가 있다. 1. 사자가 없다. 2. 왼쪽에 사자가 있다. 3. 오른쪽에 사자가 있다. 1번의 경우엔 i-1번째 줄에서 사자가 없든 어디에 있든 상관없다. 2번의 경우엔 i-1번째 줄에서 사자가 없거나 오른쪽에만 있어야 한다. 3번의 경우엔 i-1번째 줄에서 사자가 없거나 왼쪽에만 있어야 한다. 정리하자면 dp[100000][3]일 때 dp[i]..

문제 풀이 1년 반전에 자료구조 시간에 이미 배운 문제라...풀이 방법도 그때에서 전혀 달라지지 않았다. 이게 정석이기도 하구 스택에 연산자를 쌓다가 적절한 때에 출력하는게 중요한데, 여기에 연산자 우선순위를 사용한다. 다들 알겠지만 연산자의 우선순위는 괄호, 곱셈나눗셈, 덧셈뺄셈이다. 그리고 스택에 연산자를 쌓을 건데 절대로 나보다 우선순위가 높거나 같은 연산자 위에 쌓일 수는 없다. 그니까 곱셈이 이미 스택에 들어온 상태에서 덧셈이 들어오려 한다면 곱셈이 스택에서 나와야 한단 것이다. 피연산자인 A~Z는 스택에 쌓이지 않는다. 그냥 간단히 말해서 우선순위가 그 어떤 연산자보다 높다고 생각하는게 맘 편할 수도 있겠다. 그래서 이 2가지 규칙 1. 스택에 쌓이는건 오직 연산자 2. 나보다 우선순위가 높은..

문제 풀이 이 문제의 핵심은 커서 위치 정보를 따로 저장하지 않은 채 문제를 푸는 것이다. 그러려면 스택을 2개 사용해야 한다. s1에 입력을 char 단위로 쪼개어 넣었다. 커서는 처음에 문장 맨 뒤에 위치한다. 이때 커서의 왼쪽 문자는 d고 이는 s1.top과 일치한다. 그럼 각 명령에 대해 해야할 일은 무엇일까? L d를 가리키던 커서가 c를 가리키도록 해야한다. s1.top이 c가 되기 위해선 d가 없어져야 한다. 하지만 d를 완전히 없앨 수는 없다. 그래서 d를 s2에 옮겨준다. D c를 가리키던 커서가 다시 d를 가리키도록 해야한다. 그럼 s1.top이 다시 d가 되어야 한다는 것이다. s2.top에 있던 d를 다시 s1으로 옮겨온다. B 현재 커서의 왼쪽 문자를 지워야 한다. 이는 s1.to..