알고리즘/구현(6)
-
백준 5212번: 지구 온난화 (C++)
https://www.acmicpc.net/problem/5212 5212번: 지구 온난화 첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다. www.acmicpc.net 풀이 언뜻 보면 BFS / DFS 문제 같지만 섬인 부분만 체크하면 되는 조금 생각해야하는 구현 문제다. 그래프 탐색 유형처럼 접근하긴 했는데 map 에서 X 인 부분의 상하좌우를 확인했다. X 의 상하좌우가 map 의 밖에 있거나 바다일 경우 cnt 를 하나씩 늘려주었고 cnt >= 3 일때 X 를 임시로 a 로 바꿔주었다. 지도를 줄이는 부분에서 조금 생각해야할 부분이 있었는데 다시 map 을 탐색하면서 X 인 부분이 있을 때마다 최소 x, y 좌표와 최대 x, y 좌표..
2023.02.22 -
백준 9047번: 6174 (C++)
https://www.acmicpc.net/problem/9047 9047번: 6174 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스마다 한 줄에 네 자리 수(1000~9999)가 하나씩 주어진다. 단, www.acmicpc.net 풀이 단순한 구현 문제 6174가 나올 때 까지 while문을 돌려주면서 cnt를 하나씩 더해주었다. 4자리 숫자가 나오기 때문에 arr[4] 배열을 선언해서 한 자리씩 숫자를 넣어주고 정렬한 다음 최솟값에는 0번부터 3번까지 차례대로 넣어주었고 최댓값에는 3번부터 0번까지 차례대로 넣어주었다. 10을 곱해가며 자릿수를 늘려주면 최대 4자리의 최솟값과 최댓값이 된다..
2023.02.17 -
백준 2920번: 음계 (C++)
https://www.acmicpc.net/problem/2920 2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 풀이 단순 구현 문제. 솔브닥 무슨 훈장 같은거 있어서 그거 받으려고 풀었다. 조건이 2개 밖에 없길래 귀찮아서 통으로 문자열로 입력받은 후 조건에 맞게 출력시켜주었다. 이래도 되나... 허허 전체 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); ..
2023.01.26 -
백준 17128번: 소가 정보섬에 올라온 이유 (C++)
https://www.acmicpc.net/problem/17128 17128번: 소가 정보섬에 올라온 이유 첫째 줄에 소의 수를 나타내는 N과 욱제가 장난칠 횟수 Q가 주어진다. (4 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000) 둘째 줄에 N마리 소들의 품질 점수 Ai가 순서대로 주어진다. (1 ≤ |Ai| ≤ 10) 셋째 줄에 www.acmicpc.net 풀이 그림만 보았을 때 원형 큐로 구현해야할 것 같지만 넣고 빼는 과정이 없어서 그냥 배열로 진행했다. 첫번째~세번째 소가 선택될 수도 있기 때문에 배열 뒤에 세마리를 추가로 넣어주었다. 4마리씩 묶어서 곱한 값을 cow_mult 배열에 넣어준 다음 총합을 구했다. 장난칠 소가 포함된 cow_mult 배열을 총합에서 빼주고 더하는 과정이..
2023.01.21 -
백준 1292번: 쉽게 푸는 문제 (C++)
https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 풀이 최대 1000번이어서 백터를 이용해 전체 수열을 만들어주었다. 그리고 A 부터 B 까지 전부 sum에 더하여 출력했다. 전체 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int A, B; vector v; int sum = 0; cin >> A >> B; for (int i ..
2023.01.18 -
백준 1652번: 누울 자리를 찾아라 (C++)
https://www.acmicpc.net/problem/1652 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 풀이 최대 시간복잡도가 100*100이어서 완전 탐색으로 진행했다. 우선, ver, hor 변수를 선언해서 빈 공간일 때 카운트를 했다. 그리고 ' X ' 를 만나거나 끝 부분에 도착했을 때 ver, hor가 2보다 크다면 누울 공간이 나온다는 뜻이므로 ver_cnt 와 hor_cnt 에 1씩 더해주고 ver, hor를 0으로 초기화해주었다. 가로와 세로는 i 와 j를 바꿔 이중 for문..
2023.01.18