본문 바로가기

Algorithm/Baekjoon38

1965_상자넣기 ▶실버2 문제 풀이 전형적인 DP 문제. 가장 긴 증가하는 부분 수열 문제와 유사하다. 다음과 같은 형식으로 풀었다. 코드 #include #include #include #include #include #include using namespace std; int box[1001]; int dp[1001]; int main(void) { ios::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i > box[i]; dp[i] = 1; } int ans = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (box.. 2023. 3. 3.
1789_수들의 합 ▶실버1 문제 풀이 서로 다른 N개의 자연수의 합이 S라고 할 때, N의 값이 최대가 되기 위해서는 1부터 빼본다. S에서 1을 빼고, 2를 빼고, 3을 빼고 ... 계속 진행하다가 뺀 결과값이 이미 뺀 값이나 빼고 있는 값이라면 반복문을 종료하고 답을 낸다. ex) 20 - 1 19 - 2 17 - 3 14 - 4 10 - 5 = 5 (뺀 결과값이 현재 빼고 있는 값이므로 종료) => 20 = 1 + 2 + 3 + 4 + 10 (5개) ※ s값의 최댓값이 매우 크기 때문에 s가 int 형이 아닌 long long 형이어야 한다. 이거 때문에 에러났음... 코드 #include #include #include #include #include #include using namespace std; int m.. 2023. 3. 2.
1911_흙길 보수하기 ▶실버1 풀이 1. 주어진 웅덩이를 정렬한다. 2. 한 웅덩이에 대해 몫과 나머지를 구한 후 몫의 개수만큼 널빤지를 사용한다. 2-1. 나머지가 존재하면 널빤지를 하나 더 더해준다. 2-2. 나머지가 존재하지 않으면 건너뛴다. 3. 현재 위치가 웅덩이가 아니라면 다음 웅덩이의 첫 위치를 현재 위치로 설정한다. 코드 #include #include #include #include #include #include #include #include using namespace std; vector pool; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int ans = 0; int n, l; cin >> n >> l; for (int i.. 2023. 2. 28.
3190_뱀 ▶골드4 풀이 사과를 먹은 개수에 맞는 몸길이 유지, 방향 전환, 조건 만족 여부가 관건인 문제이다. 먼저 현재 방향에 맞게 앞으로 한 칸 전진 한 후, 그 자리에 사과가 존재하면 그대로, 존재하지 않으면 꼬리를 제거한다. 그리고 방향 전환 시간이 되었을 시, D일 경우 우회전, L일 경우 좌회전을 한다. 필요한 자료구조로는, ① 현재 방향을 나타내는 방향 배열(x, y 두 개) ② 방향 전환 queue(시간과 방향 두 개를 받음) ③ 뱀 몸 인덱스 queue(x, y 두 개) ④ 뱀이 지나간 여부를 나타내는 2차원 배열 ⑤ 사과가 존재하는 여부를 나타내는 2차원 배열 먼저 입력을 받고 적절한 자료구조에 데이터를 넣어준다. 현재 x위치, y위치에 현재 방향에 맞게 1칸 전진한 값을 더해준다. 그 자리에 .. 2023. 2. 10.
1874_스택 수열 ▶실버2 풀이 스택을 사용하는 문제. 예제 1번을 예시로 들면, ① [0]: 4 > 1, 2, 3 ☞ (+): push ② [0]: 4 == 4 ☞ (-): pop ③ [1]: 3 == 3 ☞ (-): pop ④ [2]: 6 > 5 ☞ (+): push ⑤ [2]: 6 == 6 ☞ (-): pop ⑥ [3]: 8 > 7 ☞ (+): push ⑦ [3]: 8 == 8 ☞ (-): pop → n이 될 때까지 진행 따로 스택을 만들어서 그 스택의 top 값과 입력 값으로 주어진 값을 비교한다. 이때, top 값과 같다면 pop top값이 더 크다면 NO를 출력하고 종료한다. 코드 #include #include #include #include #include #include #include using name.. 2023. 2. 8.
1620_나는야 포켓몬 마스터 이다솜 ▶실버4 풀이 문자열과 숫자를 구분하여 탐색해야하기 때문에 생각보다는 까다로운 문제였음! map을 이용하여 인 map 하나, 인 map 하나를 생성하여 번호를 찾을 땐 전자, 이름을 찾을 땐 후자를 이용한다. 이때, m번의 입력을 받는 동안 자료형을 구분할 수 없으므로 string 형태로 일단 받고, 그 문자열의 첫 자가 문자인지 숫자인지 구분 후 진행한다. ※ 참고 문자랑 숫자를 구분할 때, isalpha 함수를 사용했는데 런타임에러가 떴다. 쓰지말기! 코드 #include #include #include #include #include #include #include #include #include #include using namespace std; map number; map name; int m.. 2023. 2. 3.