[백준 / C++] 5557번: 1학년 (다이나믹 프로그래밍, dp)

https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 난이도: solve.ac 골드 5 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 및 구현 i - 1 번째 수까지 사이에 + 또는 - 집어넣어 계산한 결과가 j이고, 이를 만드는 경우의 수가 n개라고 해보자. 나는 이걸 이렇게 표현했다. dp[i - 1][j] = n i 번째 수(arr[i])가 x라고 하자. 그럼 위의 경우에서 i 번째 수까지 계산한 결과는 j - x 또는 j + x..

• format_list_bulleted PS/백준
• · 2023. 9. 15.
• textsms

[백준 / C++] 16637번: 괄호 추가하기 (삼성 A형 기출)

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 난이도: solved.ac 골드 3 알고리즘 분류 구현, 브루트포스 알고리즘 접근 방법 및 구현 괄호는 한 번에 최대 두 개의 숫자만 묶을 수 있으므로 괄호는 s[i]와 s[i+2]를 묶는다. s[i+2]가 문자열 크기를 벗어나지 않으면 괄호를 만들어 계산한다. 만든 괄호 안을 먼저 계산한 후, 지금까지 계산했던 결과와 함께 s[i-1]에 있는 연산자를 통해 계산한다. 괄호를 만들어 ..

• format_list_bulleted PS/백준
• · 2023. 9. 14.
• textsms

[백준 / C++] 14502번: 연구소 (삼성 SW 역량 테스트 기출)

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 난이도: solved.ac 골드 4 접근 방법 이 문제는 N과 M의 범위가 적어서 브루트포스 방식으로 풀 수 있다. 따라서 0인 부분 중 3개를 골라 벽을 세우는 모든 경우의 수를 두고 안전영역의 개수를 구했다. 0인 부분의 개수를 n이라고 하면, nC3의 경우의 수를 모두 파악해야 한다. 구현 nC3개의 경우의 수를 만드는 방법은 다음과 같다. 우선, 0인 부분의 좌표를 미리 저장해둔다. 나는 vacant라..

• format_list_bulleted PS/백준
• · 2023. 9. 12.
• textsms

[백준 / C++] 3190번: 뱀 (삼성 SW 역량 테스트 기출)

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 난이도: solved.ac 골드 4 구현 방법 board라는 2차원 배열에 뱀의 현재 모습을 그렸고, dir라는 2차원 배열에 뱀의 머리(head)가 이동했던 방향을 나타내었다. 뱀의 머리의 위치와 방향을 나타내기 위해 H라는 구조체를 만들었고, 꼬리(tail)의 위치도 저장하기 위해 T라는 구조체를 만들었다. 초기 t(시간) 값은 1로 주었고, 이동할 때마다 1씩 증가하도록 하였다. 이동할 때는 먼저 ..

• format_list_bulleted PS/백준
• · 2023. 9. 10.
• textsms

[백준 / C++] 17144번: 미세먼지 안녕! (삼성 SW 역량 테스트 기출)

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 난이도: solved.ac 골드 4 구현 방법 각 1초 동안 진행되는 과정은 T를 1씩 줄여나가며 T가 0이 될 때까지 진행해주었다. (while(T--) {...} 방식으로) 미세먼지를 확산하는 과정에서 확산으로 인한 값의 변화 때문에 미세먼지 상태를 나타내는 배열은 단 하나만으로는 부족한데, 따라서 배열을 두 개 이용했다. 각 확산된 값을 임시 배열에 저장했다가 다시 원래 배열로 복사하는 식..

• format_list_bulleted PS/백준
• · 2023. 9. 3.
• textsms

[백준 / C++] 21608번: 상어 초등학교 (삼성 SW 역량 테스트 기출)

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 난이도: solved.ac 골드 5 구현 방법 문제에서 주어진 세 가지 조건 그대로 구현하면 되는 문제다. 먼저 첫 번째 조건을 살펴보자. "비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다." 이를 구현하기 위해 학생들을 배치할 공간 board[N][N]을 만들고, board가 0인 모든 빈자리를 기준으로 인접한 상하좌우 캉을 탐색해 좋아하는 학생이 몇 ..

• format_list_bulleted PS/백준
• · 2023. 8. 28.
• textsms