Old/백준

백준 11403번 경로 찾기 // C++

문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다. 풀이 단순한 dfs 문제이다. 입력으로는 해당 점에서 다른 점까지 이어져있는지를 0과 1로 구분하여 들..

백준 9558번 Between the Mountains // C++

문제 Did you try to ride a telepherique (cable car)? It is a lot of fun. Our company is trying to build a new telepherique line between two high mountains and you will be invited for a free ride. The trick to get your free ride is to help the company in building the telepherique line. The company wants to build two platforms, one on each mountain. The line will extend between these two platforms. ..

백준 9557번 Arabic And English // C++

문제 Some computer programs have problems in displaying Arabic text, especially when mixed with English words in the same line, because Arabic is written from right to left and English is written from left to right. In this problem we will try to fix a text with some corrupted lines which consist of a mixture of Arabic and English words. For simplicity, all Arabic letters will be replaced with the..

백준 14888번 연산자 끼워넣기 // C++

문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 식의 계산은 연산자 우선..

백준 14889번 스타트와 링크 // C++

문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다. N=4이고, S가 아래와 같은 경우를 살펴보자. 스타트 팀: S..

백준 5766번 할아버지는 유명해! // C++

문제 "그 뉴스" 를 보고 온 가족이 들떴습니다. 모두들 할아버지께서 수 십년간 굉장히 실력있는 브릿지(카드게임의 일종) 선수였다는 것은 알고 있었지만, 할아버지가 역대 최고의 bridge 선수로서 기네스북에 오른다는 소식은 정말이지 놀라웠죠! IBA(국제 브릿지 협회)는 수 년간, 매주 가장 실력있는 선수들의 랭킹 정보를 기록해왔습니다. 매주 랭킹에 선수의 이름이 오를 때마다 선수의 포인트가 1포인트씩 오르는데, 할아버지께서 가장 많은 포인트를 얻어서 최고의 브릿지 선수로 선정되었습니다. 할아버지께는 그와 브릿지 순위를 경쟁하는 친구들이 많이 있었기 때문에, 할아버지는 어떤 선수(들)가 2등을 했는지 정말 궁금하셨습니다. IBA 랭킹 정보는 이제 온라인에 올라와 있고, 할아버지께서 당신에게 도움을 요청..

백준 4172번 sqrt log sin // C++

문제 도현이는 수학 숙제를 하고 있다. 문제는 다음과 같다. 다음과 같이 재귀적으로 정의된 수열이 있다. i가 주어졌을 때, xi를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 한 줄에 하나씩 주어진다. 각 줄에는 i가 주어지며, 이 수는 0보다 작지 않고, 백만보다 크지 않다. 입력의 마지막 줄에는 -1이 주어지며, 이 수는 입력의 마지막을 나타내는 수이다. 출력 입력으로 주어진 i마다 x_i를 1000000로 나눈 나머지를 출력한다. 풀이 C++에서의 cmath 라이브러리를 사용하면 쉬운 문제다. 최대 수가 백만이고, 시간 제한이 있어서 처음부터 백만까지 계산한 뒤 입력을 받고 출력을 하는 식으로 풀었다. 내림 함수 : double floor(double n..

백준 4246번 To and Fro // C++

문제 Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down Note that Mo includes only ..