본문 바로가기

분류 전체보기

 (236)
C++[백준]1748번 수 이어 쓰기 1 https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 솔루션 long long 으로 선언을 하고, 한 자리부터 1씩 더하는데, 10의 승수가 될 때 마다 수를 1씩 더 늘려주어 더해 나간다. 코드 #define ll long long int #include using namespace std; ll sum; ll N; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; ll ref = 10; ll cnt = 1; for (int i = 1; i = ref) { ref..
C++[백준]3085번 사탕 게임 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 솔루션 조금 무식하게 짜서.. 코드가 길다.. 나는 각자 앞에 문자와, 아래에 있는 문자를 교환 한 다음, 각 행, 각 열에 대해서 가장 긴 수열을 체크했다. 처음에 문제 이해를 잘 못 해서 한번 틀렸지만, 금방 고칠 수 있었다! (함수를 만들어서 짜니까 수정하기도 편한 듯?!) 코드 #include using namespace std; char arr[52][52]; int N; int cnt; int calcRowMax(int r) { int idx = 0; int maxCnt = 0; while (idx < ..
C++[백준]17103번 골드바흐 파티션 https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 솔루션 100만 까지 모든 수에 대해서 소수인지 아닌지 판단을 해 놓는다. 그리고 각 테케마다 숫자를 받으면 나누기 2 를 해 주고, 그 숫자까지 i, value - i 가 둘다 소수라면 카운트를 ++ 해 주었다. 시간초과 날 줄 알았는데, 통과가 되었다.. 코드 #define MAX 1000000 #include using namespace std; bool is_visit[1000002]; in..
C++[백준]12026번 BOJ 거리 https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 솔루션 나는 마지막 문자열부터 재귀적인 방식으로 dp를 채워나갔다. 특정 인덱스의 문자가 B라면 특정 인덱스보다 작은 인덱스 중에서, J라는 문자열 모두 찾았고 거리 값을 더해줬을 때, 그 중 최솟값을 리턴하도록 하였다. 코드 #define INF 987654321 #include using namespace std; string arr; int dp[1002]; int calcDis(int idx) { if (idx == 0) return dp[idx] ..
C++[백준]2563번 색종이 https://www.acmicpc.net/problem/2563 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 솔루션 도화지 크기가 100*100이여서, bool 타입으로 배열을 잡고, 색종이의 왼쪽 아래 지점이 입력으로 들어오면, 각각 r,c의 +10만큼 bool 배열을 true로 바꿔주었다. 바꿔주면서 만약 true가 아니었다면, 색종이가 하얀색에서 검정색으로 바뀌는 부분이므로 ++를 해 주었다. 코드 #include using namespace std; bool arr[102][102]; int main() {..
C++[백준]2566번 최댓값 https://www.acmicpc.net/problem/2566 2566번: 최댓값 첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다. www.acmicpc.net 솔루션 maxValue에 최댓값을 저장하고, i,j 를 9까지 반복시키면서 입력으로 들어 온 값이 maxValue보다 더 크다면, 그 떄 r,c를 저장 해 주었다. 코드 #include using namespace std; int N = 9; int r=1, c=1; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int ma..
C++[백준]1516번 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 솔루션 위상정렬을 사용해서 푼 문제이다. 각 건물의 짓는데 걸리는 시간과, 부모 노드를 저장 할 때, 부모노드- 자식노드간의 엣지를 저장해주고, 자식노드의 degree를 올려준다. 그리고 우선순위 큐를 정의 했는데, 시간이 가장 낮은 순으로 뽑히도록 정렬했다. 먼저 degree가 0인 것을 우선순위 큐에 담아준다. 그리고 우선순위큐를 뽑아주면서 연결된 자식 노드들의 degree를 줄여주..
C++[백준]1774번 우주신과의 교감 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 솔루션 최근에 유니온 파인드를 공부하면서 겪은 문제인데, 그 문제를 알고 있어서 그런가 접근은 생각보다 쉽게 가능했다. 다만 중간에 계산 실수가 있어서,, 디버깅 하는 데 좀 시간이 걸렸다. 먼저 우주신들의 갯수만큼 하나의 집합으로 설정하고, M 개의 입력이 들어오는 동안에 두개의 집합의 거리를 0이라 가정하고 크루스칼을 사용한다. 그리고 M이 0인 경우에는 1번 인덱스..

티스토리툴바