알고리즘/BOJ 썸네일형 리스트형 15685번 15685번 - 드래곤 커브 규칙을 명확하게 식으로 풀어내는데 어려움을 느꼈다. 그리고 주어진 문제에서 X,Y 좌표 값이 내가 평상시에 쓰던 값이랑 달라서 헷갈렸다. 규칙은 각각의 버전을 따로 나열해서 생각해보면 찾을 수 있다. 주어진 예시의 경우 버전 0일때 오른쪽 버전 1일때 오른쪽 - 위쪽 버전 2일때 오른쪽 - 위쪽 - 왼쪽 - 위쪽 버전 3일때 오른쪽 - 위쪽 - 왼쪽 - 위쪽 - 왼쪽 - 아래쪽 - 왼쪽 - 위쪽 빨간색의 경우는 이전의 버전을 그대로 따라오고, 파란색의 경우는 빨간색을 역순으로 보았을 때 왼쪽으로 90도로 움직인 것이라 볼 수 있다. 위쪽은(↑) 왼쪽으로(←) , 왼쪽은(←) 아래쪽으로(↓) ... 따라서 이에 맞게 change 함수를 구현하고 dx,dy 배열을 이용하여 문제를.. 더보기 15686번 15686번 - 치킨 배달 삼성 상반기 기출문제로 알려져 있는 문제. 오랜만에 PS를 다시 시작하니까 뭔가 감을 잃어버린 느낌... 처음에 문제가 꽤 복잡하다고 생각해서 문제를 여러번 읽어봤다. 어떤 걸 먼저 접근해서, 고정시키고 풀어야할지를 생각하면서 풀어봤다. 그러다가 치킨집을 선택할 수 있는 제한값이 낮기 때문에, 이를 이용해서 재귀함수를 구현하고, 완전탐색을 하였다. 치킨집을 최대 M개 선택할 수 있기 때문에, 1~M까지 치킨집을 모두 구해야한다. 기본적으로. 물론 최소 거리를 구하기 때문에, 가지치기를 통해서 충분히 전부하지 않고 구할 수 있을 것이라고 생각한다. (하지만 난 구현하지는 않았다.) 그리고 치킨집이 많을 수록 그 거리를 최소화 할 확률이 높기 때문에 main 함수에서 for문은 가.. 더보기 1799번 1799번 - 비숍 처음에는 N-Queen 처럼 행으로 접근했더니 시간 초과가 발생. 그 다음에는 대각선으로 생각했으나, 시간 초과 발생. 그리고 다른 사람들 힌트를 생각했더니, 홀수번째 대각선과 짝수번째 대각선은 서로에게 영향을 미치지 않는다. 그렇기 때문에 합으로 나타내서 시간을 줄일 수 있었다.( 예를들면 1억x1억을 1억+1억으로 바꾸면 시간이 확 줄듯이) 그렇게 해서 오른쪽 위로 올라가는 대각선을 짝수번째와 홀수번째로 나누었다. 처음 dfs문에서 x,y,c를 구하는 것은 각 대각선의 첫번째 값을 구하는 방법이다. 그리고 while문을 통해서 대각선의 값들을 하나씩 넣어보는 방식으로 문제를 풀었다. 이때 chk 배열은 대각선과 직각을 이루는 대각선이 사용됐는지 여부를 판단하는데 사용했다. 즉, 처.. 더보기 1063번 1063번 - 킹 간단한 시뮬레이션 문제인데, 평상시에 사용하던 맵이랑은 뒤바뀌어 있다. 그래도 그냥 맨 왼쪽 아래를 0,0 으로 놓고 생각해서 문제를 풀었다. 평상시랑 dx 배열의 값이 반대가 되어야 한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116#include#includeusing namespace std;int d.. 더보기 11559 11559번 - Puyo Puyo 시뮬레이션 문제. dfs를 돌면서, 길이가 4이상인 값들은 맵에서 전부 '.' 로 바꿔준다. era 라는 함수를 써서 dfs와 똑같이 돌면서 값을 . 으로 바꿔주는 함수를 이용했다. dfs를 이용해서는 return 을 이용해서 길이 체크하는 코딩이 생각이 나지 않아서, 값이 작아서 두번 이용했다. 그리고 다시 전체를 돌면서 이동시켜준다. 이때는 맨 밑 바닥부터 시작해서 위에 값들과 swap 시켜주는 방식으로 문제를 풀었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747.. 더보기 1793번 1793번 - 타일링 D[N] 은 2*N 직사각형을 채우는 방법의 수라고 할때 D[N]=D[N-1] + 2*D[N-2] 가 된다. 근데 이 문제의 가장 큰 문제점은 바로 답이 long long의 범위를 벗어난다는 점이다. 따라서 BigInteger 를 구현해야 하는데, 나는 이걸 구현해본적도 없고... 구현 할 생각도 없어서 인터넷에서 긁어왔다. DP부분은 밑으 go() 함수만을 보면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293.. 더보기 15559번 15559번 - 내 선물을 받아줘 처음에 단순히 연결요소의 갯수 문제라고 생각했는데, 한번 더 생각해야 했다. 내가 지금 있는 지점에서 움직일 수 있는 좌표와 내가 지금 있는 지점으로 올 수 있는 좌표를 모두 dfs를 통해서 체크하였다. 그래서 연결 요소가 총 몇개가 나올 수 있는지를 확인하면 되는 문제였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102#include#includeusing name.. 더보기 2484번 2484번 - 주사위 네개 은근 헷갈리는 문제였다. 배열을 1~6까지 만들고, 나온 갯수만큼 배열을 ++해준다. 그리고 4개 나온경우, 3개 나온경우, 2개 2개 경우를 체크해준다. 그러면서 1이 나온 값은 계속 sum에 갱신을 한다. 그리고 for문을 빠져나왔을 때 2개 나온 경우를 체크해주고, 최대값과 비교해준다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include#include#includeusing namespace std; int main(){ //freopen("input.txt", "r", stdin.. 더보기 이전 1 2 3 4 5 6 7 ··· 40 다음