문제 문제 바로가기> BOJ 1918번: 후위 표기식 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이 #include #include #include #define MAX 32001 using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); string expr; cin >> expr; stack st; // 우선 순위가 낮은 연산자 (+, -) 부터 큰 연산자 (*, /) 순으로 쌓임 // 연산자 우선 순위 : () > *..
문제 문제 바로가기> SWEA 5653번: 줄기세포 배양 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 1. 배열의 범위 세포가 (비활성 + 활성) 상태를 가지므로 N+2*K가 아닌, N+K로만 잡아줘도 충분하다! 넉넉히 +1 해주는 버릇이 있다. 혹시 모르니까,, start를 K/2로 해주면, 배열의 범위를 벗어날 일은 없어서, 따로 검사해주지 않아도 된다. 2. 하나의 그리드 셀에 동시 번식하려고 하는 경우 생명력 수치가 높은 줄기 세포가 해당 그리드 셀을 혼자서 차지한다. 따라서 생명력 수치가 높은 줄기 세포부터 번식 하면 되고, 이를 위해 Priority Queue를 이용했다! 처음에 2차원 배열..
문제 문제 바로가기> SWEA 2115번: 벌꿀채취 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 1. 부분집합을 이용하여, 해당 지점(y, x) 에서 얻을 수 있는 가장 큰 수익을 profit[y][x]에 저장한다. 2. 조합을 이용하여, 일꾼 두명이 얻을 수 있는 최대 수익을 구한다. JAVA import java.io.*; import java.util.*; public class Solution { static BufferedReader br = null; static int N, M, C, ans; static int[][] map, profit; static void input() throws..
문제 문제 바로가기> BOJ 17615번: 볼 모으기 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 풀이 크게는 총 2가지 경우가 있고, 그 안에서 또 2가지로 나뉘어 총 다음과 같은 4가지 경우가 있다. 1. 빨간 볼을 움직이는 경우 왼쪽으로 움직이는 경우 오른쪽으로 움직이는 경우 2. 파란 볼을 움직이는 경우 왼쪽으로 움직이는 경우 오른쪽으로 움직이는 경우 위 4가지 경우에서 최솟값을 찾아주면 되는 간단한 문제였다 ㅎㅎ 처음에 너무 복잡하게 생각하려고 하다보니 오히려 어렵게 느..
문제 문제 바로가기> BOJ 17822번: 원판 돌리기 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 풀이 원판을 2차원 배열로 입력받아서 시뮬레이션을 진행하는 문제였다. 처음에 시간을 절약하기 위해 M/2 < k 인 경우 반대 방향으로 M-k만큼 돌려주었고, sum, cnt 변수를 전역 변수로 가지고 있는 방식을 이용했다. 하지만, 이러한 부분을 빼고 그때그때 sum과 cnt를 가져오는 함수를 만들도록 코드를 변경하면, 코드가 더 깔끔해질 것 같았고, 시간 초과가 발생할 시간 복잡도도 아니어..
문제 문제 바로가기> BOJ 17825번: 주사위 윷놀이 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 풀이 각 칸에서 이동해야하는 다음칸, 점수를 저장해 두어야 하는데, 이 때 약간의 노가다 작업?이 필요하다. 그 외에는 단순 백트래킹 문제이다 ! 💡 문제 해결 Point 처음에 파란지점 때문에 2차원 배열([이동칸][현위치] = 다음위치)을 만들어서 바로 이동하게 하려고 했는데, 이렇게 하는 경우, 너무 많은 노가다 작업이 필요했다,, 개인적으로, blueP 지점을 별도 배열로 가지고 있는 부분이 중요한 ..
문제 문제 바로가기> BOJ 21611번: 마법사 상어와 블리자드 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 풀이 문제에서 요구하는 각 스텝의 구현이 모두 비슷해서 구현이 어렵지는 않은 문제였다. 다만... 모든 반례가 통과하는데, 왜 자꾸 75%에서 틀리지,, 라고 생각했는데... 바로 `if(x==0) break; ` 부분을 넣어주지 않았기 때문 ... x=0 이 되는 시점에서는 어떠한 처리도 할 필요없고, 해서도 안된다,,,!!!!!! 🥲 이 처리를 해주지 않으면, change_ma..
문제 문제 바로가기> BOJ 21758번: 꿀 따기 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 풀이 벌 2마리와 벌통의 위치를 모두 다르게 설정해보는 방식으로 문제를 푼다면 시간 초과가 발생한다. 벌이 2마리, 벌통이 1개이므로, 총 3가지의 경우가 있다. 1. 벌 벌 벌통 이 경우, 첫 번째 벌은 가장 왼쪽에 있는 게 이득이다. 따라서 반복문 O(N)을 통해 두 번째 벌의 위치를 지정해주고, 그 시점에서 얻을 수 있는 이익을 계산한다. 2. 벌 벌통 벌 이 경우, 첫 번째 벌은 가장 왼쪽에, 두 번째 벌은 가장 오른쪽에 있는 게 이득이다. 따라서 반복문 O(N)을 통해 벌통의 위치를 지정해주고, 그 시점에서 얻을 수 있는 이익을 계산한다. 3...
문제 문제 바로가기> BOJ16946번: 벽 부수고 이동하기 4 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 매번 벽을 만날 때마다 dfs 혹은 bfs 탐색을 진행하면, 복잡도가 O(N^2*M^2)이고, N과 M 은 최대 1000이므로, 시간초과가 발생한다! 이동 가능한 곳의 영역을 미리 체크해 놓는다면, 시간 복잡도를 O(N^M)으로 줄일 수 있다. 예를 들어 예제 2번의 경우, 4 5 11001 00111 01010 10101 다음과 같이 이동가능한 영역의 size?를 미리 체..
문제 문제 바로가기> BOJ 17471번: 게리맨더링 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 #include #include #define MAX 11 #define INF 100001 using namespace std; int N; int ans = INF; int total = 0; // 총 인구 수 int people[MAX]; // 구역의 인구 수 bool visited[MAX]; // 방문 여부 저장 int isgroup1[MAX]; // 그룹 1에 속하는지 vector v[MAX]; // 각 구역과 인접한..
문제 문제 바로가기> BOJ 2110번: 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 #include #include #define INF 1000000001 #define MAX_HOME 200001 using namespace std; int N, C; int home[MAX_HOME]; void input() { cin >> N >> C; for (int i = 0; i > home[i]; sort(hom..
문제 문제 바로가기> BOJ 2343번: 기타 레슨 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 매개 변수 탐색을 이용해서 가능한 블루레이의 크기 중 최소를 구하는 문제다. 주의할 점은 상한(high)을 설정하는 부분이다. 처음에 high를 10,001으로 설정했는데 바로 틀렸다,, 생각해보니, 각 강의의 길이가 10,000분을 넘지 않는 것이지, 블루레이의의 크기는 당연히 10,000분을 넘을 수 있기 때문!! 이 부분을 주의해 줘야 할 것 같다! 각 강의당 길이가 10,000분이므로, 10000*1000..
문제 문제 바로가기> SWEA 5644번: 무선 충전 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 input에서 주어진 경로를 따라 이동하면서, 다음과 같은 두 가지 경우로 나누어 문제를 해결해주면 된다. 1. 두 사용자가 동일한 위치에 있는 경우 → 또 다시 3가지 경우로 나뉜다 1) 주변에 충전 가능한 bc가 없는 경우 → continue 2) 1가지 bc를 나눠 사용해야 하는 경우 → 1개의 bc를 각각 나눠 사용한다. 어짜피 ans에 나눠서 더하나, 그 값을 더하나 같다. 3) 2가지 이상의 bc가 있는 경우 → 제일 큰 파워를 가진 두 bc를 이용한다. (나는 prioirty queue를 이용..
문제 문제 바로가기> BOJ 6987번: 월드컵 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 풀이 경기가 진행될 수 있는 모든 경우의 수를 탐색하여, 그 중 하나라도 결과 값과 일치하는 게 있다면 (= 가능한 결과), 1을 출력하도록 풀었다. 모든 경우의 수를 탐색할 경우, 시간 복잡도는 3^15(=14,348,907)(*4 = 57,395,628)로 시간 내 완전탐색이 가능하다! 총 경기 경우의 수는 6C2 = 15 이고, (이 조합을 미리 만들어주는 부분이 make_team() 함수) 두 팀이 경기를 진행..
문제 문제 바로가기> BOJ 16974번: 레벨 햄버거 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, www.acmicpc.net 풀이 패티가 늘어나는 규칙은 " (이전 레벨 패티) * 2 + 1 " 이다. N 0 1 2 3 4 5 ... patty 1 3 7 15 31 63 ... 햄버거의 아래 X장을 먹는 경우에는 총 3가지 경우가 있다. (재귀적으로, 분할정복으로 해결하기 위해) 1. (해당 레벨의) 가운데 패티보다 적게 먹는 경우 : get_patty(n-1, x-1) = 레벨을 낮추어 재귀적으로 탐색해준다. x-1..