Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/백준oj

https://www.acmicpc.net/problem/18232 18232번: 텔레포트 정거장 첫 번째 줄에 정수 N, M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300,000, 0 ≤ M ≤ min(N×(N-1)/2, 300,000)) 두 번째 줄에 정수 S, E가 공백으로 구분되어 주어진다. (1 ≤ S, E ≤ N, S ≠ E) 그 다음 줄부터 M www.acmicpc.net 풀이 먼저 입력을 받으면서 텔레포트 정거장을 그래프를 이용해서 연결해주었습니다. 그런 뒤, S부터 시작하며 BFS를 실행하여 E까지의 최단거리를 구했습니다. 1. 해당 정거장이 텔레포트 정거장이면, 연결된 정거장들을 통해 최단거리를 비교하며 진행합니다. 2. 다음정거장이 범위안에 있으면, 최단거리를 비교하며 진행합니..

2022. 12. 18.

문제풀이/백준oj

https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. www.acmicpc.net 풀이 간단한 DP문제입니다. DP[N] = 2*N의 타일을 배치할 수 있는 경우의 수라고 한다면, 아래의 설명과 같은 논리로 인해 일반식이 완성이 됩니다. 1. 2*N의 타일은 2*(N-1)의 타일에 2*1타일을 세로로 배치하면 되기때문에 DP[N-1]일때의 개의 경우의 수가 생깁니다. 2. 2*N의 타일은 2*(N-2)의 타일에 2*1 타일 두개를 나란히 가로로, 세로로 배치하거나 2*2 타일을 배치하면 되기때문에 DP[N-2] * 3의 경우의 수가 생깁니다. 3. 하지만 ..

2022. 12. 15.

문제풀이/백준oj

https://www.acmicpc.net/problem/13022 13022번: 늑대와 올바른 단어 첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 'w' = 0, 'o' = 1, 'l' = 2, 'f' = 3 으로 인덱스를 정해준 뒤, 문자열을 탐색하면서 조건을 확인해주었습니다. 이전 알파벳의 인덱스 == 현재 알파벳의 인덱스 이 경우에는 해당 인덱스의 cnt를 갱신시켜 줍니다. 이전 알파벳의 인덱스+1 == 현재 알파벳의 인덱스 이 경우에는, 이전 알파벳의 인덱스를 갱신시켜주고, 현재 알파벳의 개수를 갱신시켜줍니다. 현재 알파벳이 w인경우(새로운 wolf의 시작점인 경우) 현재까지 나온 w,o,l,f의 개수가..

2022. 12. 6.

문제풀이/백준oj

https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 풀이 친구와 친구의 친구까지 초대를 한다고 했으므로, 그래프를 생각했다. 먼저 친구관계를 그래프로 나타내준 뒤, 1번부터 bfs를 이용하여 depth가 2인 친구들까지의 수를 세어주면된다. 이때 상근이의 depth는 0으로 설정을 해준다. 아래의 코드는 상근이 자신을 포함하므로, -1을 해준 결과를 출력해주면된다. 시간복잡도 O(N+M) 코드 import java.util.*; cl..

2021. 12. 26.

문제풀이/백준oj

https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 풀이 DP를 이용해서 문제를 해결했다. 먼저 해당지점에서 점프했을때, dp[next]보다 더 작은횟수로 도달할 수 있다면 갱신을 해준다. 이때 점프를 했을때 범위를 넘어가면 안되므로 조건을 추가해준다. 코드 import java.util.Arrays; import java.util.Scanner; public class Main { static int[] v; static int[] d..

2021. 10. 27.

문제풀이/백준oj

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 dp[i][j]=k 라고 할때, i번째열에서 j번째 스티커를 골랐을떄 ( 0 = 첫번째 스티커 / 1 = 두번째 스티커 / 2 = 아무것도 선택 x ) 0번째~i번째 열까지의 스티커점수의 최댓값을 k라고 하자. 먼저 1. i번열에서 첫번째 스티커를 고르기 위해서는 i-1번 열에서 두번째 스티커를 고른경우와 i-1번 열에서 아무것도 고르지 않은 경우가 있다. 이 두 경우중에서 더 큰..

2021. 8. 31.

문제풀이/백준oj

https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 풀이 N의 값이 매우 작으므로, 완전탐색을 이용해서, 겹치지 않게 서로다른 위치에 3개를 놓을때마다 최솟값을 갱신하는 방법으로 값을 구했다. 보통의 완전탐색과 같은데, 이제 꽃을 심으면 동,서,남,북,중앙 5군데를 차지하므로, 이것을 고려해서 문제를 해결해주면 된다. 코드 #include #include using namespace std; int maze[10][10]; bool flower[..

2021. 8. 30.

문제풀이/백준oj

https://www.acmicpc.net/problem/1633 1633번: 최고의 팀 만들기 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플 www.acmicpc.net 풀이 모든 선수를 탐색하며, 만약 현재까지 백팀에 15명이 안찼을때 백팀에 넣은경우, 흑팀에 15명이 안찼을때 흑팀에 넣은경우, 어느 팀에도 넣지 않은경우 3가지와 현재상태중 최댓값을 넣어주면된다. 이때 DP의 Memoization을 이용해서 시간을 단축시켜준다. 또한 문제에서 주어진 입출력의 종료조건이 따로 주어지지 않아서 scanf로 받고, EOF가 아닐때까지로 조건을 주었다. 코드 #..

2021. 8. 24.