나 요리학원 출신임

90도로 방향을 바꾸기 위해서는 거울이 1개 필요하다 이 때 C -> C까지 갈 때 최소 거울을 찾는 문제다 다익스트라를 이용해서 d[100][100][4]로 각 방향으로 갈 때 최소비용을 구했다 만약 90도 방향이 바뀐다면 그때만 비용을 +1 해줬다 마지막 도착지에서는 4방향 중 가격이 가장 싼 곳을 출력하면 된다 다른 사람들 풀이를보니 그냥 bfs만 돌려도 충분히 풀 수 있다 내가 방향이 바뀌면 새로운 점들을 queue에 비용을 증가시켜 넣고 현재 정점에서는 다시 한칸 앞으로가서 비용없이 또 탐색을 하면 된다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 3..

매일 풀어야지 풀어야지 하다가 안풀고있던 문제다 완전탐색으로 풀 수 있는데 이런 복잡한 구현문제는 확실하게 해야한다 계속 대충대충 생각하고 채점디버깅을 이용하니 반례가 넘처난다..! 최대 4방향 5번이므로 4^5 각각 이동시키는데 최대 20^2 정도 되니까 다 찾아봐도 된다! 이동시키는 move 함수 빼고는 평범하게 모든 경우를 고르는 코드다 move 함수에서는 방향에 따라 x,y좌표를 잡고 앞에있는 숫자부터 숫자를 옮기고 숫자가 합쳐졌는지 check배열을 통해 확인한다 그래서 숫자가 가다가 check=false인 같은 수를 만나면 합치고 check=true로 바꿔주자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..

java를 이용해서 문제를 풀어봤다 먼저 모든 방법의 수는 4^10이므로 2^20이랑 같고 완탐으로 충분히 가능하기 때문에 모든 경우의 수를 돌려봤다 4방향을 한번씩 가면서 dfs를 이용하면 된다 방향을 정한 다음에는 R > B > R 순서대로 공을 굴려봤다 R을 두번 굴리는 이유는 R이 B 뒤에있어서 B에 막힌다면 B가 움직이고 똑같은 거리만큼 더 가야하기 때문에 한번 더 보내보는 경우다 근데 답을 체크해주는 부분을 함수에서 잘못 설정해서 모든 경우를 못봤다 그래서 틀렸다..!!! 복잡할수록 천천히 신중하게 코드를 짜야겠다..! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ..

완전탐색을 통해 찾을 수 있는 문제다 모든 단어는 antc로 시작하고 tica로 끝나므로 최소 antic 문자는 배워야한다! 5개!! 그럼 알파벳 21개중에 내가 k-5개를 골라서 그 알파벳들로 최대로 배울 수 있는 문장수를 찾으면 된다! 비트를 통해 알파벳을 고르고 하나하나 확인해보자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #include #include #include using namespace std; int n,k,ans;..

백트래킹을 이용해 풀 수 있는 문제다! 근데 막풀면 틀린다 처음에 그냥 있는그대로 넣고 구하고 생각해보니 시간이 20^10이였다 ㅋㅋㅋ 구간의합의 부호를 주기 때문에 수를 고르고 구간의 합을 확인 후 가능하면 넘기면 된다! 근데 헷갈리는 부분은 같은 수를 중복으로 못쓰는 줄 알았는데 사용가능하다..! 중복으로 사용 못하게 풀면 틀린다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include using namespace std; int n; char op[12][12]; int psum[12],ans[12]; bool check(int..

유명한 N-Queen 문제다! 백트래킹을 통해 찾을 수 있다 여기서 핵심은 내가 한 행을 기준으로 보면 된다는 것이다 그럼 한 행을 잡고 그 안에서 퀸을 놓을 수 있는 열을 찾고 다음 행으로 가는 것이다 그렇게 행을 끝까지 도착하면 경우의수가 1개 증가한다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include using namespace std; int n,ans; bool check[22][22]; int dx[2] = {-1,-1}; int dy[2] = {-1,1}; bool inner(int x,int y)..

순열을 이용해 해결할 수 있는 문제다 기억해야할건 순열을 쓰기전에 정렬시키고 사용해야 한다는 것! 그걸 잊고있다가 오랜시간이 걸렸당.. 사용되는 알파벳을 찾아두고 순열로 점수를 매겨서 최댓값을 찾아보면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #include #include #include #include using namespace std; int n; int a[11],b[111]; bool c[30]; string sa[11]; int main(){ scanf(" %d",&n); for(int i=0;i>sa[i]; ..

순열을 이용해 풀 수 있는 문제다! 숫자를 최대 10개 사용하기 때문에 다 넣어보고 부등호를 만족한다면 그 중 가장 큰것과 작은것을 찾아내면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include using namespace std; #define ll long long ll M = 0; ll N = 1e12; int maxn[11],minn[11]; char op[11]; int a[10]; int n; bool check(){ for(int i=0;ia[i+1])) retur..

유명한 문제다! 근데 오랜만에 dp보다가 틀렸따! 먼저 dp식을 생각해보자 d[n] = n을 마지막으로 하는 가장 긴 수열로 생각하면 된다! 처음에 d[n]은 n까지 보면 가장 긴 길이라고 생각하다가 틀렸었다 n은 1000이기 때문에 그냥 for문을 돌면서 나를 기준으로 앞으로 가면서 나보다 작은수를 만날때마다 내 앞에 올수있는 것 중에서 나보다 길이가 긴 애를 가져가면 된다! 그럼 수열은 어떻게 구하면 될까? stack을 타고간다는 생각으로 나는 내 앞에 오는 작은 수만 생각하면 된다 그럼 가장 긴 수열이 만들어졌을 때 계속 내 바로 앞 숫자만 호출하면 수열이 완성된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..

123더하기에서 조건이 추가되었다 바로 연속된 숫자는 사용할 수 없다는 것이다 그럼 어떻게 문제를 해결해야할까 우리는 테이블에 하나의 정보를 더 저장하면 된다! 바로 마지막 숫자다 숫자 n을 만들 때 마지막이 1이라면 n-1을 만드는 경우의 수에서 마지막이 2,3인 경우만 더하면 된다 이런식으로 나머지도 채워나가면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include using namespace std; #define ll long long const ll mod = 1e9+9; i..