본문 바로가기

𝓡𝓸𝓸𝓶𝟣: 𝒜𝓁𝑔𝑜𝓇𝒾𝓉𝒽𝓂/알고리즘 문제 풀이

(26)

BOJ9095 : 1, 2, 3 더하기 (Silver 3) 너무 오랜만에 DP 풀었더니 어케하는건지 완전 까먹었는데 인터넷에 치자마자 떠오름 DP == 점화식 세우기 그래서 DP 기본 문제는 코딩보다는 수학문제 푸는 것 같은 느낌이 든다.. 처음에 이상한 짓하다가 인터넷의 힘을 빌려 힌트를 얻었고, 그 답은 dp[i] = dp[i-3] + dp[i-2] + dp[i-1] 예로, a5를 구한다고 해보면 a4 즉 4를 만드는 방법에 전부 +1 한 것 + a3 즉 3을 만드는 방법에 전부 +2 한 것 + a2 즉 2를 만드는 방법에 전부 +3 한 것 이 바로 5를 만드는 방법의 전부이다. (2) + 3 (3) + 2 (4) + 1 괄호 안의 수를 나타내는 방법은 이미 앞에서 구해놨으니, 그 방법에다가 각각 3, 2, 1을 더하면 됨 #include int dp[12]..

BOJ2468 : 안전영역 (Silver 1) 우선 나는 make_safezone으로 safe_zone 배열에 침수되는지 아닌지를 저장해주었다. rain_height보다 높이가 높으면 1, 낮거나 같으면 0으로 영역이 1로 가시적으로 보이게 만들어줌 그리고 나서 count_safezone 해서 만들어 둔 safezone의 영역 크기를 DFS를 활용해 세어주었다. 이 과정을 rainheight 0부터 100까지 반복해 최댓값을 찾아주면 끝! #include #include #include using namespace std; int height[100][100] = {0,}; int safe_zone[100][100] = {0,}; int N = 0; void make_safezone(int rain_height); int count_safezone(..

BOJ3184 : 양 (Silver 1) https://www.acmicpc.net/problem/3184 오랜만에 돌아온 PS~~~^~^ 여러분 혹시 한 번에 맞은 기분이 어떤지 아시나요 일단 저는 압니다 ㅎ히히ㅣ히히 지금 당연히 뭐하나 예외 있겠지 하고 냅다 돌려봤는데 갑자기 100% 뜨고 맞았습니다 떠서 소리지를뻔함 정말 오랜만에 백준 다시 풀고 있는데 어째서인지 한참 공부할 때보다 머리가 더 팽팽 잘 돌아가유,,, 옛날엔 실버 1 이렇게 빨리 못 풀었었는데... 그럼 설명을 해보겠습니당 1. 우선 기호를 전부 숫자로 바꿔 이차원 배열 map에 저장해준다 보자마자 왜인지 기호 그대로 냅두면 내가 너무 헷갈릴 것 같아서 그냥 싹 다 숫자로 변형해서 저장해주었습니다 사실 뭐 실행 속도에 엄청 큰 제약이 있는 그런 문제였으면 굳이 안하는게 더 ..

BOJ5671 : 호텔 방 번호 (Silver 5) #include using namespace std; int main() { while (1) { int N, M; int count = 0; cin >> N >> M; if (cin.eof()) break; for (int i = N; i

BOJ14889 : 스타트와 링크 (Silver 3) #include using namespace std; int N; int map[21][21]; int ans = 100000000; bool is_visited[21]; void DFS(int player, int cnt) { if (cnt == N / 2) { int score1 = 0; int score2 = 0; for (int i = 1; i

BOJ 2503 : 숫자야구 (Silver 5) #include #include using namespace std; int number; int strike, ball; vector array; void Filtering(int num, int s, int b) { vector newarray; vector::iterator iter; int strike = 0, ball = 0; for (iter = array.begin(); iter != array.end(); iter++) { int strike = 0, ball = 0; // cout

BOJ17404 : RGB거리2 (Gold 4) #include using namespace std; int cost[1000][3]; long long costDP[1000][3]; long long result[3]; //long long result = 1000 * 10000 + 1; void makeDP(int N) { for (int j = 0; j < 3; j++) { costDP[0][0] = 1000 * 10000 + 1; costDP[0][1] = 1000 * 10000 + 1; costDP[0][2] = 1000 * 10000 + 1; costDP[0][j] = cost[0][j]; for (int i = 1; i < N; i++) { costDP[i][0] = min(costDP[i - 1][1], costDP[i - 1][2]) ..

BOJ1149 : RGB거리 (Silver 1) #include using namespace std; int cost[1000][3]; long long costDP[1000][2]; void makeDP(int N) { costDP[0][0] = cost[0][0]; costDP[0][1] = cost[0][1]; costDP[0][2] = cost[0][2]; for (int i = 1; i < N; i++) { costDP[i][0] = min(costDP[i - 1][1], costDP[i - 1][2]) + cost[i][0]; costDP[i][1] = min(costDP[i - 1][0], costDP[i - 1][2]) + cost[i][1]; costDP[i][2] = min(costDP[i - 1][0], costDP[i - 1][1..

BOJ11660 : 구간 합 구하기 5 (Silver 1) #include using namespace std; int map[1025][1025]; long long sum[1025][1025]; void sumMaker(int N) { for (int i = 0; i > M; int x1, x2, y1, y2; for (int i = 1; i map[i][j]; } } sumMaker(N); for (int i = 0; i > x1 >> y1 >> x2 >> y2; cout

BOJ2012 : 등수매기기 (Silver 3) #include #include using namespace std; int N; int prerank[500001]; long long rankingSystem() { long long angry = 0; for (int i = 1; i > N; for (int i = 1; i > prerank[i]; } sort(prerank + 1, prerank + N + 1); cout

이전 1 2 3 다음

티스토리툴바