궤도

문제 풀이 각 선수가 몇 번 타자가 될 지는 next_permutation으로 구하면 된다. 다만, 1번 선수가 4번 타자인건 고정이니 2~9번 선수들에 대해서만 순열을 돌리고 4번 타자가 된 선수와 1번 선수를 바꾸면 되겠다. 점수나 다음 타자는 이닝이 바뀌어도 누적되는 결과니까 전역변수로 처리하면 된다. 그리고 1, 2, 3루 각 플레이트에 선수가 있는지 없는지를 저장해야 하는데...나는 비트 마스킹을 썼다. 1110 : 1, 2, 3루에 주자 존재 0100 : 2루에 주자 존재 1010 : 1, 3루에 주자 존재 가장 오른쪽 비트는 이번에 나선 타자를 위해 남겨뒀다. 아무튼 이런식으로 하면 주자 이동도 3루타 일때 (1011)

문제 풀이 할게 많아보이는데 그렇게 많진 않다. 1. 두 선거구로 나눈다. 2. 두 선거구의 인구 차이를 구한다. 3. 두 선거구를 올바르게 나눴다면 인구 차이의 최솟값을 갱신한다. 2번과 3번의 순서가 바뀌어야 하지 않나?라고 생각할 수도 있다. 근데 인구 차이를 먼저 구하고 그 값이 현재의 최솟값보다 크거나 같다면 3번을 실행하지 않을 것이다. 그럼 불필요한 연산을 하지 않으니 시간이 좀 줄어들 것이다. 두 선거구를 나누는 조합 연산은 비트마스킹으로 했다. 소스코드 #include #include using namespace std; vector split, visited; vector population; vector graph; int calcDiff() { //두 선거구의 인구 차이 int bl..

문제 풀이 이 문제의 풀이를 쓰는 이유는... 문제를 풀고 다른 사람들의 풀이가 궁금해서 블로그를 봤더니 거의 다 하드코딩(?)을 했더라 내가 짠게 엄청 좋아보이진 않지만 그래도 최대한 효율적으로 쓰려고 노력해서 올려본다. 말로 설명하기가 좀 그래서 코드를 보면서 설명하려는데 그 전에 이걸 봐두면 좋다. 내 코드에선 각 cctv의 범위가 이렇게 세트로 묶여 있다. 무슨 말인지는 코드를 보면 이해될 것이다. 소스코드 #include #include #include using namespace std; typedef pair pp; int N, M, result = 65; vector board; vector cctv; //cctv 위치 pp direction[4] = {{-1, 0}, //상 {0, 1},..

문제 풀이 일단 주어진 도미노의 총 개수는 36개이므로 이 도미노들의 정보와 사용여부를 map으로 관리하기로 했다. 그리고 빈 공간을 발견할 때마다 가로 또는 세로로 배치할 수 있는 도미노를 찾아보는데 1 1 1 상하좌우로 배치할 필요없이 그냥 2개의 방향만 고려하면 된다. 위 또는 왼쪽으로 배치하는건 이전 경우에서 고려됐을 것이기 때문이다. 아무튼 그래도 하나의 위치에 대해 최대 4개의 경우를 고려해야 한다. (가로세로)*(도미노 방향 2) 하나의 도미노에 적힌 숫자는 다르기 때문에 해당 위치에 이 도미노가 들어갈 수 있을지 확인할 때 도미노를 쪼개서 각각 고려해도 문제가 없다. https://myunji.tistory.com/202 [백준] 2580번 : 스도쿠 문제 풀이 입력을 어떻게 처리하여 어떤..

문제 풀이 솔직히 어려워서 힌트를 봤다. 난 절대 떠올리지 못했을 방법이었다. 일단 이 문제는 비트마스크이다. 2차원 배열에 어떻게 비트마스크를? 싶을 수도 있겠지만 0~(1 tmp; for (int j = 0; j < M; j++) matrix[i][j] = tmp[j] - '0'; } for (int i = 0; i < (1 tmp; for (int j = 0; j < M; j++) matrix[i][j] = tmp[j] - '0'; } for (int i = 0; i < (1

문제 풀이 문제가 참 긴데 사실 마지막 문단을 빼곤 쓸데없는 말이다. 입력값 처리의 벽만 넘으면 아주 못 풀 문제는 아니다. 일단 한줄로 들어온 저 input을 예쁘게 정리하면 - + 0 + + + + - - + 이렇게 된다. S[i][j] = A[i]+A[i+1]+...+A[j]라고 했다. 그럼 S[0][0] = A[i]인 것이고 S[i][i]에는 A[i]의 부호가 있는 것이다. 나름 괜찮은 정보인데 다 풀고보니 난 이 정보를 사용하지 않았다. A[0]부터 A[3]까지의 순서로 값을 구할 것이다. A[0]은 A[0]0, A[1]>0이어야 한다. (0, 1), (1, 1) A[2]은 여기에 또 추가로 A[0]+A[1]+A[2]=0, A[1]+A[2]>0, A[2]> input; int pos = 0; f..

문제 풀이 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..