Algorithm, Data structure/Solved Algorithmic Problem 120

BAEKJOON 3085 - 사탕 게임

문제: https://www.acmicpc.net/problem/3085 문제Little Ivan is bored at math class so he decided to play popular game called "Bomboni". At the beginning all fields of N×N square board contain candies (not necessarily of same color). When its his turn player should swap two neighbouring (up, down, left or right) candies of different color and then pick some sequence (in row or column) of same color ca..

BAEKJOON 1932 - 숫자삼격형

문제: https://www.acmicpc.net/problem/1932 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (Figure 1)Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base.Each step can go either diagonally down to the left or diagonally down to the right.The number of rows in the triangle is ≥ 1 but ≤ 500.The numbers i..

BAEKJOON 1149 - RGB거리

문제: https://www.acmicpc.net/problem/1149 memoization을 이용한 동적 계획법으로 풀 수 있는 문제입니다. 첫 번째 집을 칠할 때는 전에 칠한 집의 색이 없으므로 모든 색을 칠할 수 있기에 rgb 값 0~2이 아닌 3을 넘겨줍니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#pragma warning (disable:4996)#include #include #include #include using namespace std; int cost[1000][3];int cache[1000][4]; int dp(int curHouse, int preColor..

BAEKJOON 1158 - 조세퍼스 문제

문제: https://www.acmicpc.net/problem/1158 유명한 josephus 문제입니다. linked list 을 이용해 풀었습니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#pragma warning (disable:4996)#include #include #include #include #include using namespace std; void josephus(int n, int m){ list survivors; for (int i = 1; i

BAEKJOON 2343 - 기타 레슨

문제: https://www.acmicpc.net/problem/2343 이진 탐색으로 풀 수 있는 문제입니다. 필요한 블루레이의 개수가 m보다 많을 경우 low 를 높여 블루레이의 크기를 크게 만드는 방향으로 탐색을 하고 필요한 블루레이의 개수가 m과 같거나 더 작을 경우 블루레이의 크기를 작게 만드는 방향으로 탐색을 해서 최적의 값을 구하면 됩니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#pragma warning (disable:4996)#include #include #inc..

BAEKJOON 1992 - 쿼드트리

문제: https://www.acmicpc.net/problem/1992 분할정복 문제입니다. 시작점과 크기를 인수로 받아 해당 영역이 모두 같은지 확인을 한 후 같지 않다면 4 구역으로 분할해 재귀 호출을 하여 풀어봤습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#pragma warning (disable:4996)#include #include #include #include using namespace std; int n;bool tree[65][65]; void compress(int startY, int startX, int size){..

BAEKJOON 2792 - LJUBOMORA

문제: https://www.acmicpc.net/problem/2792 문제A marble factory has donated a large box of marbles to a kindergarten. Each marble has one out of M different colours. The governess needs to divide all the marbles between the N children in her group. It is acceptable if some children don't get any marbles. However, no child wants marbles of different colours – in other words, all marbles that a child ..

BAEKJOON 1072 - 게임

문제: https://www.acmicpc.net/problem/1072 앞선 문제들과 같이 이진 탐색으로 쉽게 풀 수 있는 문제입니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#pragma warning (disable:4996)#include #include #include #include using namespace std;typedef long long ll; bool isChanged(int x, int y, ll mid){ ll oldValue = (ll)y * 100 / x; ll newValue = (mid + (ll)y) * 100 / (x + mid); return n..