BOJ
-
[16953] A → BBOJ 2021. 10. 4. 15:01
https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net A부터 출발하면 언제 1을 붙여야 하는지를 알기 어렵지만 B부터 출발하면 언제 1을 붙였을지는 자명하다. 현재가 21이라는 상태라고 생각해보면 이 다음이 42인지, 211인지를 판단하는건 어렵지만 이전에 10.5라는 수는 정수가 아니므로, 2에서 출발했다는 한가지 경우밖에 남지 않는다. 이는 일의자리가 1인 모든 경우까지 확장이 가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include using namespace std; t..
-
[1080] 행렬BOJ 2021. 10. 3. 13:29
https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 3*3씩 토글할때, 왼쪽 위를 기준점으로 잡는다고 생각해보자. 가능한 기준점의 위치는 R : [0, n-2], C : [0, m-2]이다. 어처피 하나의 칸의 버튼을 2번이상 누를 필요는 없으므로, 버튼을 누르거나, 안누르거나 둘중에 하나를 선택해야한다. 다만 기준점이 바뀔 수 있는 타이밍은, 기준점을 토글할때 뿐이므로 버튼을 눌러야 하는가에 대한 판별은, 기준점의 원소가 행렬 B와 다른지로 판별이 가능하다. ..
-
[1744] 수 묶기BOJ 2021. 10. 3. 13:15
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 양수이든 음수이든, 2개를 곱하면 항상 양수이다 -> 절대값이 큰 수부터 차례대로 곱해나가면 된다. 다만, 양수와 음수를 곱하면 음수가 되므로 양수와 음수는 별도로 분리하여 생각해야 한다. 양수 혹은 음수가 홀수개만큼 존재하는 경우, 이는 곱하지 않고 각각 더해주어야 한다. 다만, 0이 존재한다면 마지막 음수는 0과 묶어줄 수 있으므로 더하지 않는다. 또한 양수 1같은 경우 항상 개별적으로 더하..
-
[1059] 좋은 구간BOJ 2021. 10. 3. 00:11
https://www.acmicpc.net/problem/1059 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 입력을 받고, 정렬한다. 정렬을 한다면 선형적으로 탐색을 진행하다 포함해야하는 숫자 n을 초과하는 시점에 break를 걸어줌으로써 구간 시작점의 최소값인 start와 구간 종료지점의 최대값인 end를 찾을 수 있다. 한가지 주의할점은 start = v[i-1], end = v[i]가 아닌,(off by one) 구간내 수가 입력된 수에 속하지 않아야 하기에 start = v[i-1] + 1, end = v[i] - 1으로 설정해 주어야 한다. 좋은 구간이 되기 위해서는, 구간의 길이가 2인것부터 탐색하면 되..
-
[20056] 마법사 상어와 파이어볼BOJ 2021. 10. 2. 19:40
https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 이 문제에서 구현이 어려운 포인트는 아래와 같다. "1번 행은 N번 행과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다" -> 한마디로, 선형이 아닌 원형이다 "파이어볼은 4개의 파이어볼로 나뉘어진다", "질량이 0인 파이어볼은 소멸되어 없어진다" -> 이 부분이 왜 어려운지 의문이 생길 수 있는데, 단순하게 구현할 경우, 가령 for(i=0; iA v..
-
[1261] 알고스팟BOJ 2021. 10. 2. 18:04
https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 꽤 다양한 풀이가 있을 수 있는 문제이다. 현재 위치를 정점으로 생각하면, 상하좌우로 연결된 그래프라고 생각할 수 있다. 다음 정점이 0인경우, 가중치가 0인 간선이 존재하는 셈이고 다음 정점이 1인경우, 가중치가 1인 간선이 존재하는 셈이다. 문제를 이렇게 변형한다면 1만개의 정점, 0 혹은 1의 가중치를 갖는 양방향 그래프에서 [1,1]->[M,N] 다익스트라로 해결이 가..
-
[9019] DSLRBOJ 2021. 10. 2. 11:03
https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net L 연산은 cur%1000*10으로 d2, d3, d4 3자리를 구성한 뒤 cur/1000을 더해주어서 구현한다. R연산도 L연산과 마찬가지로 구현해주면 되겠다. 출력해야하는 값, 즉 명령어의 순서를 파악하기 위해서 현재 정점을 {현재 숫자(int), 명령어의 순서(string)}으로 구성했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..
-
[1697] 숨바꼭질BOJ 2021. 10. 1. 16:47
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 아래 문제와 함께보길 권장합니다. https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc..
-
[9012] 괄호BOJ 2021. 10. 1. 16:38
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 스택을 사용하면 조금 더 직관적으로 구현이 가능합니다. 다만 스택을 사용할때 사용하는 것은 스택의 size() 뿐이므로 '('와 ')'가 입력된 횟수를 저장할 변수만으로도 올바른 괄호인지를 판별할 수 있습니다. x : '('가 등장한 횟수 y : ')'가 등장한 횟수 위처럼 구성할때, x
-
[4344] 평균은 넘겠지BOJ 2021. 10. 1. 16:34
https://www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. www.acmicpc.net 점수를 입력받자마자 누적하고, n으로 나누어 평균을 구합니다. 평균을 구한 뒤, 다시 배열을 순회하며 평균과 비교하여, O(N) + O(N)으로 평균을 넘는 학생의 수를 구하고 이를 바탕으로 조건에 맞게 출력하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include int main(void) { int i, j, c, n, sum, a[1000], m, cnt; scanf("%d", &c); for (i = 0; i