목록전체 글 (616)

1일1알

백준 11052번 카드 구매하기 C++

한정된 공간 안에 최대한의 가치를 넣는 배낭 채우기와 비슷한 문제이다. 카드의 개수가 무게, 가격을 가치라고 생각하면 된다. 하지만 한가지 다른 점이 있는데, 한 종류의 카드팩을 여러번 살 수 있다는 것이다. 점화식을 세우기 위한 과정을 우선 top-down 방식으로 생각해 보면 이런 식으로 그려볼 수 있다. 설명을 해보자면, 루트는 우리가 최종 구해야 할 답이고, N개의 카드를 최대한의 가격으로 구매할 때의 가격이다. 왼쪽으로 나눠진 부분은 4번 카드팩을 구매했을때의 상태이다. 4번 카드팩을 구매해서 카드의 개수가 4만큼 줄어들어서 0이 되었고, 카드팩은 구매했다고 사라지는게 아니기 때문에 사용가능한 카드팩은 그대로인 모습이다. 그리고 구매한 카드팩의 가격을 더해준 것이다. 오른쪽으로 나눠진 부분은 4..
알고리즘 2021. 10. 23. 14:33
백준 17070번 파이프 옮기기 1 C++

파이프를 오른쪽으로 옮길 때에는 현재 위치에서 오른쪽 한 칸이 비어있어야 하고 아래로 옮길 때에는 아래에 한 칸이 비어있어야 한다. 대각선으로 옮길 때에 주의해야할 점이 있는데, 대각선으로 간 칸과, 그 위칸과 왼쪽 칸 모두 비어있어야 한다는 것이다. 문제에도 비어있어야 할 칸이 색으로 칠해져있다. 나는 구조체를 만들어서 파이프의 위치와 현재 상태(오른쪽, 대각선, 아래 중 하나) 정보를 저장하고 그 구조체를 큐에 넣어서 bfs방식으로 해결하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; str..
알고리즘 2021. 10. 22. 12:16
백준 1051번 숫자 정사각형 C++

간단한 브루트포스 문제이다. 모든 칸을 돌면서 오른쪽, 아래쪽으로만 검사하면서 정사각형이 되는지 확인하고 크기가 커질때마다 크기를 갱신해주었다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; string str; vector v(n, vector(m)); for (int i = 0; i >..
알고리즘 2021. 10. 21. 12:21
백준 12851번 숨바꼭질2 C++

bfs로 풀 수 있는 문제인데 특이한 점은 가장 빠른 시간만 구하는 게 아니라 그 방법이 몇 가지인지까지 구해야 한다. 최초 도달했을 때 시간을 구하고 그 시간과 같은 시간에 도착 할때마다 Count를 증가시켜주면 된다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; vector visited(100001, false)..
알고리즘 2021. 10. 20. 12:46
백준 16953번 A->B (C++)

bfs로 문제를 해결하였다. 초기 cnt=1 처음 큐에 pair로 (A, cnt)을 넣고 (A * 2, cnt + 1) 와 (A * 10 + 1, cnt + 1)을 bfs로 탐색하면서 A의 값이 B의 값과 같아지면 cnt를 출력하는 방식으로 해결하였다. 같은 숫자를 또 방문하는 것을 방지하기 위해 탐색 시간 복잡도가 O(1)인 unordered_set에 방문한 값을 넣어줘서 중복을 방지하고, A * 2나 A * 10 + 1이 B보다 커지면 큐에 넣지 않는 식으로 구현하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef lo..
알고리즘 2021. 10. 19. 10:45
백준 11660번 구간 합 구하기 5 C++

dp 테이블을 이용하여 누적 합을 저장해서 풀 수 있는 문제이다. 예제의 숫자들을 각 행마다 누적 합을 저장하여 저장한다. (2,2)부터 (3,4) 까지의 합은 이 부분의 합을 구하면 되기 때문에 dp[2][4]-dp[2][2-1] + dp[3][4]-dp[3][2-1] = (14 - 2) + (18 - 3) = 27 이렇게 구할 수 있다. 이것을 코드로 나타내면 #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin...
알고리즘 2021. 10. 18. 13:19
이전 Prev 1 ··· 99 100 101 102 103 Next 다음