본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 9184번 : 신나는 함수 실행 www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 메모이제이션으로 불필요한 함수 호출을 막는 dp문제였습니다. 풀이방법 1. w라는 함수를 실행하기 전에 d[a+50][b+50][c+50]값이 저장되어 있는지 확인하는 ret 참조변수를 선언 후 저장합니다. a,b,c값이 음수를 포함하므로 음수 인덱스에 접근하지 않도록 오른쪽으로 50만큼 당겨주어 저장했기 때문에 읽을 때 +50한만큼 인덱스를 가져옵니다. 2. w함수를 수행한 결과를 포맷에 맞게 출력합니다. Cod..
(C++) - 백준(BOJ) 1049번 : 기타줄 www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 패키지로 구입할 때의 최소 금액과 낱개로 구입할 때의 최소 금액을 각자 저장합니다. 2. 구입 방식을 3가지로 나누어 각자 방식에 따라 금액을 구합니다. 2-1. n개 이상으로 줄을 패키지로 구입할 때 2-2. n개 만큼 줄을 낱개로 살 때 2-3. n개 미만으로 최대한 패키지로 산 후 나머지를 낱개로 살 때 3. 이들 중 최소값을 출력합니다. Code #include..
(C++) - 백준(BOJ) 1058번 : 친구 www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net brute force로 친구 사이의 거리가 2이하인 간선을 세는 floyd warshell 문제였습니다. 풀이방법 1. 친구 i,j사이의 거리를 구합니다. i,j로 가는 거리보다 i -> k -> j로 가는 거리가 더 짧을 때 거리를 갱신하는 방식으로 모든 친구들에 적용합니다. 2. 구한 거리 배열 dist를 모두 순회하며 i의 모든 친구 사이의 거리가 2이하라면 세줍니다. 매번 i가 바뀔 때마다 최대값을 저장합니..
(C++) - 백준(BOJ) 1743번 : 음식물 피하기 www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진 www.acmicpc.net bfs문제였습니다. 풀이방법 1. 현재 좌표에 쓰레기가 있고 방문하지 않았다면 쓰레기의 영역 크기를 bfs를 통해 구합니다. 2. 쓰레기 영역들 중 가장 넓은 크기를 출력합니다. Code #include using namespace std; using pii = pair; int dx[] = {0,0,-1,1}; int dy[] = {-1,1,0,0}; int pas..
(C++) - 백준(BOJ) 14654번 : 스테판 쿼리 www.acmicpc.net/problem/14654 14654번: 스테판 쿼리 첫째 줄에 라운드의 수 N이 주어진다. (1 n; for(int i = 0; i > teamA[i]; for(int i = 0; i > teamB[i]; for(int i = 0; i < n; i++){ if(teamA[i] == 1 && teamB[i] == 2) cntA = 0, cntB++; else if(teamA[i] == 2 && teamB[i] == 3) cntA = 0, cntB++; else if(teamA[i] == 3 && teamB[i] == 1) cntA = 0, cntB++; else if(teamB[i] == 1 && teamA[i] == 2) ..
(C++) - 백준(BOJ) 16236번 : 아기 상어 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net bfs문제였습니다. 풀이방법 1. 먹을 수 있을 때까지 계속 먹이탐색, 이동합니다. 먹을 수 있는 물고기의 거리들을 모두 구합니다. bfs를 이용해 거리정보를 상하좌우 모두 구해줍니다. 지나갈 수 있는 공간은 아기상어보다 작거나 같은 물고기들이 있는 곳이나 0인 부분입니다. 만약 해당 공간의 물고기 크기가 현재 아기 상어의 크기보다 작으면 거리정보와 해당 공간의 행,열 좌표를 vector에 넣어줍니다. ..
(C++) - 백준(BOJ) 16234번 : 인구 이동 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net bfs문제였습니다. 풀이방법 1. 각 국가당 인구를 입력받습니다 2. 이동 할 인구가 없을 때까지 다음을 수행합니다. 2-1. 국경을 열어 연합을 형성했을 때의 인구 지도를 만듭니다. bfs를 통해 인접국가의 차이가 l이상 r이하일 때 같은 연합입니다. 이때 서로 다른 연합의 국가 또한 인접해 있을 수 있습니다. 이 경우 인접은 했으나 차이가 조건에 부합하지 않기 때문에 다른 연합이라고 표시합니다..
(C++) - 백준(BOJ) 5212번 : 지구온난화 www.acmicpc.net/problem/5212 5212번: 지구 온난화 첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다. www.acmicpc.net 시뮬레이션 문제였습니다. 풀이방법 1. 지도를 입력받습니다. 2. 바다로 될 경우는 'X'의 상하좌우(인접한 곳)이 바다이고 3칸 이상일 때입니다. 비교할 상하좌우 칸이 지도를 넘어가는 경우에도 바다이므로 세줍니다. 세준 이후에는 바다로 될 지형을 ' '으로 바꿔줍니다. 3. 'X'인 곳을 정답 배열 ans에 옮겨줍니다. 4. ans의 'X'가 등장하는 최소 최대의 행,열을 구해준 뒤 해당 영역만큼 출력합니다. Code #include #include using namespace std;..

티스토리툴바