11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 1. 문제 설명 예제 입력 2의 경우 4 > -4 > -2 루프를 반복하면 무한대로 작아지기 때문에 -1을 출력한다. 예제 입력 3의 경우 1번 도시와 3번 도시가 연결되어 있지 않으므로 2번째 줄에 -1을 출력한다. 2. 구현 아이디어 1 - 출력 초과 C < 0인 경우, 즉 음의 간선이 있기 때문에 벨만 포드 알고리즘을 사용한다. 벨만 포드는 음의 간선이 존재할 때 사용하는 최단 거리 알고리즘이다. ..

1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 1. 문제 설명 위 예제이서는 7 - 3 - 8 - 7 - 5 를 선택했을 때가 최대가 되는 경로이므로, 수들의 합인 30을 출력한다. 2. 구현 아이디어 1 - 맞았습니다 !! DP가 적용될 수 있는 조건은 동일한 작은 문제들이 반복하여 나타나는 경우 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 나타낼 수 있는 경우 이다. 윗 줄에서 구한 합을 현재 줄에서의 최댓값을 구하는데 사용하며(1번 조건 충족), 윗 줄에서 구한 합에 따라 현재 줄에서의 수의 합이 달라지므로(2번 조건 충족) DP를 사용해서 풀 수 있다. D..

16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다 !! 최근 비트마스킹에 익숙해지고자 비트마스킹 유형 문제들을 모아서 풀고 있다. 비트마스킹을 사용한다는 것을 알면 쉽게 풀 수 있다. N=4일 때, 0001: 1번 문제를 고름 0010: 2번 문제를 고름 0011: 1, 2번 문제를 고름 0100: 3번 문제를 고름 . . . 이런 식으로 경우의 수를 정수로 표현한다. 그리고 반복문을 사용하여 AND 연산을 사용해서 만약 i번째 자리(뒤에서 시작하며 0부터 시작)가 1일 경우, 해당 문제를 벡터에 저장해둔다. 그리고 원소들의 합, 최댓값, 최솟값을 구해 주어진 조건에 맞으..

15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 삼성 알고리즘 특강 사전 문제를 풀면서 비트마스킹에 어려움을 느껴 비트마스킹 관련 문제를 풀어보았다. 1. 문제 설명 2. 구현 아이디어 1 - 시간 초과 비트마스킹을 활용하여 k번 사람이 어느 팀에 속했는지 표현하였다. N=4일 때, 0은 링크 팀에 속해있고 1은 스타트팀에 속해있다는 의미이다. 0000: 모든 팀원이 링크 팀 0001: 1,2,3번 사람은 링크 팀, 4번은 스타트 팀 0011: 1,2번은 링크 팀, ..

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1. 문제 설명 암호의 조건을 다시 정리하면 아래와 같다. 1개 이상의 모음이 있어야 함 2개 이상의 자음이 있어야 함 암호를 이루는 알파벳이 증가하는 순서일 것 2. 구현 아이디어 1 - 시간 초과 구현 문제라고 생각하고, 순열을 구할 때 사용하는 next_permutation을 활용하여 문제에 주어진 조건대로 구현하였다. 하지만 결과는 시간 초과 🥲 #include using namespace std; int l, c; vector v; char vowel[5] ..

1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 이전에 파이썬으로 푼 적이 있는 문제인데 데이터 추가로 재채점이 된 이후 시간초과로 틀린 문제 처리되어 이번에 C++로 다시 풀어보았다! 1. 문제 설명 예제 입력 1의 경우 C-A-D, 예제 입력 2의 경우 H-A-D-G-J-F로 갈 경우 최대여서 각각 3, 6을 출력한다. 2. 구현 아이디어 1 - 맞았습니다 !! 최대로 움직일 수 있는 칸, 즉 가장 '깊게' 들어갈 수 있는 칸 수를 세어야 하므로 DFS를 사용해야 한다. 이미 지나온 알파벳인지..