고인물을 지양하는 블로그

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net $D_{i,j}$ 를 다음과 같이 정의하자. $D_{i,j} : C_{i}$ 원 까지 이용해 j원을 만드는 경우의 수 따라서 $C_{i}$ 원을 이용하는(할 수 있는) 경우, 이용하지 않는 경우 두 가지 경우로 나눌 수 있다. 각각의 경우는 이다. 따라서 점화식은 다음과 같다. 코드 1 #include #include #include int N,K; bool boun..

영어 디버프 받아서 그런 거라고 믿고 싶습니다 ㅎ.ㅎ 뒤에서 1100등 정도 했네요 정말 마음 아픕니다.

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입 www.acmicpc.net #include #include struct Edge {int x,y,w; bool operator a.w; } //..

디버깅 15분 포함 약 1시간 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net BOJ 7569 토마토(3차원)와 거의 같은 문제이다. 전역 큐를 사용해 bfs 함수의 매개변수를 없애려..

코딩 15분, 디버깅 1시간 - STL은 잘못이 없다. https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net #include #include #include using namespace std..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은, 섬들을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서 www.acmicpc.net 입력은 0과 1로 주어진다. 1은 섬을 나타내고 0은 바다를 나타낸다. 2중 for loop로 입력 배열(visited)를 탐색하다 ..

금요일부터 가볍게 BFS/DFS 기초 문제들을 풀어보았다. 정답률이 높은 순으로 100026 적록색약, 2583 영역 구하기, 1926 그림, 7562 나이트의 이동 문제를 풀었는데 사실 큰 틀은 거의 똑같고, 문제에 따라 연결 요소, 연결 요소의 개수 등.. 의 차이가 있었을 뿐으로 거의 같은 문제들이었다. 2583번 영역 구하기의 경우 왼쪽 아래를 원점으로 카테시안 좌표계로 문제의 입력이 주어지는데, 배열에서 사용하는 좌표계의 그것과는 달라 머릿속에서 바로 떠오르지 않아 꽤나 곤욕스러웠다. 7562번의 경우 위 문제들과 마찬가지로 BFS를 이용했는데, 최단거리 문제로 접근했다. BFS를 수행하며 도착하는 위치마다 이동에 필요한 횟수를 업데이트 하는 방법으로 문제를 해결했다. #include #incl..

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()( www.acmicpc.net 결론부터 말하자면 첫 알고리즘은 실패했다. #include #define Pair pair using namespace std; int m..