EQ1의 짱무말 갓잔치 EQ1의 짱무말 갓잔치

처음에는 이 문제를 어떻게 풀어야 하나 싶었는데 사실 지금도 어떻게 풀어야 맞는 것인지는 모르겠다. ㅎㅎ;; 왠지모르게! 그냥! 최장길이증가수열(LIS)의 길이를 구한다음에 전체 길이에서 빼주면 그게 답이 되지 않을까? 라고 생각했다. 그냥 어렴풋한 생각으로는 번호 순서대로 서 있다는게 결국에는 증가수열로 서 있다는 것이기 때문에 기존 수열에서 LIS를 구하고 LIS는 그대로 고정! 그리고 나머지를 올바른 위치로 샥샥 옮기면! 증가수열 완성! 예를 들어서 3 7 5 2 6 1 4 에서 LIS는 3 5 6이다. 따라서 남은 1 2 4 7을 자리에 맞춰서 샥샥 끼워맞추는 식이다. #include using namespace std; int n; int seq[202]; int lis[202]; int mai..

흑흑 상근아... 왜 그런 취미를 가지고 있니ㅠㅠ 좀 더 유익한 취미를 가지렴.. 차라리 스도쿠를 하는게 어떻겠니....? 처음 문제를 봤을 때 숫자를 임의로 더하고 빼면 한 번 계산할 때마다 가짓수가 2배가 되는데 이게 가능한건가? 싶었는데 잘 보니 우리 상근이는 1학년이라서 숫자를 0부터 20까지 밖에 모른다고 한다. 오.. 상근아... 고마워!! 따라서 어떻게 계산을 하더라도 계산의 결괏값 즉, 치역은 21개 밖에 존재하지 않는다는 뜻이다. 마침 수열의 최대 갯수도 99개이기 때문에 100 * 21 짜리 배열을 만들어서 저장해두면서 사용하도록 하자. dp[i][j] 수열의 i번째 항까지 계산을 했을 때 j라는 값이 될 경우의 수 문제의 구조는 기본적인 냅색문제와 같다. dp[i][j]는 dp[i-1..

처음 문제 읽고 든 생각이 '아 이거 왠지 수학적 지식이 있거나 조금 더 연구를 해보면 완전 아름다운 코드를 짤 수 있을 것 같아!'였다. 하지만 그런걸 생각하기 귀찮으니 그냥 정석적인 DP로 풀도록 하자...ㅎㅎ 기본적인 풀이 방법은 이렇다. a번째 행렬부터 b번째 행렬까지 곱하는데 필요한 최소 계산 횟수를 calCnt[a][b]라고 하자. a번째 행렬부터 b번째 행렬까지 어떻게 곱할것이냐면! a번째부터 k번째까지 곱한 행렬에다가 k+1번째부터 b번째까지 곱한 행렬을 곱할 것이다. calCnt[a][b] = calCnt[a][k] + calCnt[k+1][b] + 두 행렬을 곱하는데 필요한 계산 횟수 두 행렬을 곱하는데 필요한 계산 횟수 = a번째 행렬의 행 개수 * k번째 행렬의 열 개수 * b 번째..

난 이 문제에 불만이 많다! 일단 팰린드롬이 뭔지 설명조차 제대로 안되어있다. 아니 어떻게 1, 2, 1은 팰린드롬이고 2, 1, 3, 1은 팰린드롬이 아니다. 라는 문장만 보고 아하 팰린드롬은 대칭인 형태를 의미하는구나! 라고 알 수 있단말인가? 대칭 수열인지, 커졌다 작아지는 바이토닉한 수열인지 아니면 1, 2, 1, 2, 1, 2 이렇게 반복되는 수열인지 알게뭐람? 결국 인터넷에 검색해보고나서야 팰린드롬이 대칭인 수열을 의미한다는 사실을 알았다. 고쳐라! 백준! 그리고 또 하나는 시간 제한인데... 사실 이건 뭐 내 지식 부족이긴 하지만 잘한것을 틀렸다고 하는건 화난다! 위의 이유로 화내는 김에 그냥 같이 문제에게 화낼테다. 나는 C++로 코딩할 때 scanf나 printf보다는 cin, cout을..

만약 평범한 DP 문제였다면 그렇게 어렵지 않았을 것이다. 하지만 이 문제가 골드 4인 이유는 메모리 제한 때문이겠지! 그래서 원래라면 100000 * 3 짜리 2차원 array를 3개 정도 만들어서 기록하면서 진행했겠지만 그렇게하면 메모리 초과가 발생하기 때문에 한 줄 입력을 받을 때마다 바로 계산하는 방식으로 했다. 계산 자체는 그렇게 어렵지 않다. 문제에서 설명하는 그대로 max함수와 min함수를 이용해서 계산하면 된다. #include #include using namespace std; int n; int map[3], maxCnt[3], minCnt[3]; int main() { cin >> n; for(int i = 0; i > map[0] >> map[1] >..

사육되는 판다의 평균 수명이 30년이므로 이 판다를 위해서는 적어도 대나무가 잘 정렬된 100 * 100의 숲을 준비해야한다! 전형적인 DFS/BFS로 보이지만 그렇게 풀면 시간초과가 나기 때문에 DP를 써야하는 문제이다. 사실 이쯤되면 DFS/BFS는 DP의 하위 개념이 아닌가 싶다. 아무튼 여기서 사용한 livingDay(x, y)라는 함수는 이 판다가 (x, y)의 지점부터 시작할 때 몇 일 살 수 있는가를 return해주는 함수이다. day라는 2차원 배열을 참고해서 이미 day[x][y]가 구해져있다면 그 값을 그냥 return 구해져 있지 않다면 값을 1로 초기화를 한 후, 4방향에 대해서 livingDay를 구해서 제일 큰 값을 취한다. 근데 의문을 가질 수 있는게 '이미 방문한 곳을 다시 ..

바이토닉 수열이라는 명칭이 되게 생소하긴 하지만 개념 자체는 어렵지 않았다. 바이토닉 부분 수열을 선 그래프로 그렸을 때 깔끔하게 산 모양이 나오면 되는거다! (물론 값이 극단적이면 깔끔하진 않겠지...) 아무튼 나는 이 문제를 11053번 : 가장 긴 증가하는 부분 수열의 응용으로 풀었다. 아쉽게도 내 블로그에는 11053번의 풀이가 없어서 11053번의 약간 심화 문제인 14002번 : 가장 긴 증가하는 부분 수열 4의 풀이법을 링크 걸어둔다. 개념은 다음과 같다. 가장 긴 증가하는 부분 수열을 정순(앞에서부터) 구해서 len이라는 배열에 저장해둔다. 그리고 역순(뒤에서부터)으로 한 번 더 구해서 revLen이라는 배열에 저장해둔다. 그리고 마지막에 len + revLen - 1의 값이 제일 큰 것이..

휴... 어떻게 얼기설기 풀었다. 어려운 문제일수록 뭔가 아름답게 푸는 방법이 있을 것이라는 생각이 드는데 음... 나는 사실 문제를 푸는게 우선이라서 아름다운 코드를 생각할 단계가 아니라는 생각이 든다. 아무튼 이 문제는 11053번 문제의 심화버전이다. 11053번이 단순히 길이만을 출력하는 문제라면 이 문제는 그 수열 자체를 출력해야 하는데 각 항이랑 연결된 위치를 나타내는 con이라는 수열을 추가했다. (con은 connect의 약자다) len이 제일 긴 녀석을 미리 저장해둔 뒤 len이 제일 긴 (예시에서는 index = 5가 제일 길기 때문에) 50에서 con을 따라 역행한다. con = 3이므로 index = 3인 30으로 가고 30의 con = 1이므로 index = 1인 20으로 간다. ..