BOJ
[BOJ] 1484 - 다이어트
문제 출처 백준 1484 - 다이어트 풀이 엔토피아가가 선물해준 저울로 젠 G 킬로그램이 주어지면 성원이의 현재 몸무게로 가능한 것을 모두 구하는 문제였습니다. G 킬로그램 = {성원이의 현재 몸무게}2 - {성원이가 기억하고 있던 몸무게}2 G는 100,000 보다 작거나 같기 때문에 무작정 큰 수까지 돌려서 제곱 - 제곱의 조합을 찾기에는 시간초과가 날 것입니다. 그래서 어떤 상한선이 있을 것이라 생각했고 수가 커질수록 제곱 - 제곱의 결과가 커진다는 것을 알아내어 제곱 - 제곱의 결과가 G보다 커지는 경우 더이상 몸무게를 찾지 않도록 해주었습니다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development by creating ..
[BOJ] 20152 - Game Addiction
문제 출처 백준 20152 - Game Addiction 풀이 어떤 칸 x에 도달하는 최단 경로를 저장해주는 배열(map)과 x에 최단 경로로 도착할 수 있는 모든 경로들의 갯수를 저장해주는 배열(acc)을 따로 선언해주어야 합니다. - 큐에 데이터를 넣지 않는 경우 1. x에 도달했을 때 최단 경로가 아닐 경우 2. x가 이미 최단 경로가 갱신되어 있는 경우 즉, x에 최단 경로로 최초로 도달했을 때 방문 표시를 해주고 이후에 최단 경로로 도달하는 경로들은 x위치에 경로의 갯수만 저장해주는 것입니다. 위와 같이 진행했을 때 목적지에 최단 경로로 도달할 수 있는 모든 경우의 수를 구할 수 있습니다. 그 이유는 다음과 같습니다. 큐는 선입선출(FIFO) 자료구조 입니다. 먼저 들어온 데이터가 먼저 나가는 ..
[BOJ] 15898 - 피아의 아틀리에 ~신비한 대회의 연금술사~
문제 출처 백준 15898 - 피아의 아틀리에 ~신비한 대회의 연금술사~ 풀이 연금술사 피아가 3개의 재료(4×4 형태)를 적절히 선택하고 배치하여 가마(5×5 격자 모양)에 넣어 만들 수 있는 최대 품질의 폭탄을 만드는 문제였습니다. 품질은 원소와 효능을 합해 구해주어야 합니다. 원소는 R, B, G, Y, W가 있었는데, W인 경우는 아무런 점수도 얻을 수 없고 나머지 품질의 경우는 각 원소별로 효능을 모두 더해 품질 = 7R + 5B + 3G + 2Y 이처럼 곱해주는 작업을 통해 품질을 구해줍니다. 우선 3개의 재료를 고르는 경우는 완탐을 통해 모든 순열의 경우의 수를 고려해주었습니다. 재료를 돌리거나 위치를 다르게 넣어주는 등 재료가 가마에 들어가는 16가지 경우를 모두 배열로 만들어 16 × 1..
[BOJ] 18291 - 비요뜨의 징검다리 건너기
문제 출처 백준 18291 - 비요뜨의 징검다리 건너기 풀이 비요뜨가 1번 징검다리에서 마지막 징검다리까지 도달하여 강을 건너는데 경우의 수를 구하는 문제였습니다. 경우의 수가 2N-2의 규칙을 가지고 있고 징검다리의 개수가 최대 109까지 이기 때문에 그대로 계산한다면 109 + 7로 나눈다고 해도 너무 큰 수가 되버려 long long 범위를 넘어가버립니다. 따라서 (28) -> ((22)2)2 이런 식으로 재귀함수를 돌려 계산해주었습니다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development by creating an account on GitHub. github.com
[BOJ] 16197 - 두 동전
문제 출처 백준 16197 - 두 동전 풀이 문제의 핵심은 두 가지라고 생각했습니다. 1. 두 동전 중 하나만 보드에서 떨어뜨려야 한다. 2. 동전을 움직이는 버튼은 최대 10번까지만 누른다. 동전을 움직이는 버튼을 10번보다 많이 눌러야 한다면 더이상 버튼을 누르지 않기 때문에 동전이 움직이는 경우의 수의 최대가 다음과 같았습니다. 41 + 42 + . . . + 410 따라서 경우를 모두 돌려도 시간초과가 나지 않을 것이라 예상했습니다. 동전을 위, 아래, 왼쪽, 오른쪽으로 움직여서 탐색하는 bfs를 사용했습니다. 문제에 나와있는 그대로 움직이는 것을 구현해서 모든 경우를 봐주어 최소 값을 구해주었습니다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Al..
[BOJ] 2502 - 떡 먹는 호랑이
문제출처 백준 2502 - 떡 먹는 호랑이 풀이 주어진 날이 x라면 x-1날은 주어진 날 전날을 말합니다. x(떡의 갯수) - x-1(떡의 갯수) = x-2(떡의 갯수) 즉, 주어진 D째 날에서 전날의 떡의 갯수를 빼주는 방식으로 전전날의 떡의 갯수를 구했습니다. x-1(떡의 갯수)를 구하기 위해서 현재 날짜의 떡의 갯수보다 작은 경우를 모두 가정하여 빼주었습니다. 예를 들어 7번째 날의 떡의 갯수가 7개라면 6~1까지 떡의 갯수를 빼주었습니다. 주어진 D째 날의 떡의 갯수에서 전날의 떡을 빼주는 과정을 D만큼 반복하여 첫째 날까지 나누어 줄 수 있는지 직접 돌려 보았다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development b..
![[BOJ] 7795 - 먹을 것인가 먹힐 것인가](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbwWfra%2FbtqR1Fb0b2a%2FjRZNHi91OTHXSKwPHvLrl0%2Fimg.png)
[BOJ] 7795 - 먹을 것인가 먹힐 것인가
문제 출처 백준 7795 - 먹을 것인가 먹힐 것인가 풀이 심해에 사는 생명체 A는 자신보다 크기가 작은 B를 먹습니다. B를 내림차순 정렬해서 A와 비교해주면 A가 B보다 큰 경우에는 해당 B부터 더 작은 B들을 먹을 수 있다는 의미 입니다. 또한 A 생명체는 자신보다 작은 B를 찾기 위해 모든 B를 찾을 필요가 없습니다. A를 오름차순 정렬해서 B와 비교해주게 되면 현재 A가 이전 A보다 더 작을 것이기 때문에 이전 A가 마지막으로 비교했던 B부터 비교해주면 됩니다. 코드 C++ small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development by creating an account on GitHub. github.com Java small..
[BOJ] 17281 - (야구공 모양의 아이콘)
문제 출처 백준 17281 - 야구 풀이 개인적으로 구현이 복잡한 문제였다고 생각했습니다. 완전 탐색을 통해 타순을 정해주었습니다. play함수는 타순을 정해주고 그 순서대로 이닝을 진행하여 얻을 수 있는 점수를 구했습니다. 타석(home배열)에 선수가 있는지 3루부터 확인하여 진루시켜주었습니다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development by creating an account on GitHub. github.com